Distributed Subtyping

One of the most frequent operations in object-oriented programs is the "instanceof" test, also called the "subtyping" test or the "type inclusion" test. This test determines if a given object is an instance of some type. Surprisingly, despite a lot of research on distributed object-oriented languages and systems, almost no work has been devoted to the implementation of this test in a distributed environment. This paper presents the first algorithm to implement the "subtyping" test on an object received through the wire, without having to download the full code of the object type, nor to deserialize the object. We use a slicing technique that encodes a (multiple-subtyping) hierarchy using as little memory as the best known centralized implementation of the "subtyping" test. Our slicing technique is however different than centralized ones and allows for the dynamic addition of types without global reconfiguration. We convey the practicality of our algorithm through performance measures obtained from a fully distributed implementation of our algorithm which we experiment on standard Java hierarchies. In particular, we show that we can perform a subtyping test between 3 and 12 times faster than the code downloading approach without hampering the time taken for deserialization. Moreover, we require the same subtyping time as a string-based approach while reducing the encoding length by a factor of 50.