Efficient Distributed Subtyping Tests

Subtyping tests are essential in typed publish/subscribe infrastructures, especially when the underlying programming language supports subtype conformance, as in Java or C#. These tests are particularly challenging when the publish/subscribe infrastructure is distributed, because processes have diverging views and new types may be added in a decentralized manner. Maybe surprisingly, subtyping tests for such distributed systems have been devoted only little attention so far; they are usually strongly intertwined with serialization and code transfer mechanisms. This paper presents an efficient subtype testing method for event objects received through the wire, requiring neither the download of a full description of the types or classes of these objects nor their deserialization. We use a slicing technique that encodes a multiple subtyping hierarchy with as little memory as the best known centralized type encoding, but allows for the dynamic addition of event types without re-computing the encoding. We convey the practicality of our approach through performance measures obtained with standard Java libraries in a publish/subscribe system. Our approach performs between 3 and 12 times faster than a code transfer approach without adding overhead to object deserialization, and requires the same testing time as a straightforward string-based type encoding while reducing the encoding length by a factor of 50.