Programming with Live Distributed Objects
Krzysztof Ostrowski†, Ken Birman†, Danny Dolev§, and Jong Hoon Ahnn†
†Cornell University, and §The Hebrew University of Jerusalem
†{krzys, ken, ja275}@cs.cornell.edu, §dolev@cs.huji.ac.il
Abstract. A component revolution is underway, bringing developers improved productivity and opportunities for code reuse. However, whereas existing tools work well for builders of desktop applications and client-server structured systems, support for other styles of distributed computing has lagged. In this paper, we propose a new programming paradigm and a platform, in which instances of distributed protocols are modeled as “live distributed objects”. Live objects can represent both protocols and higher-level components. They look and feel much like ordinary objects, but can maintain shared state and synchronization across multiple machines within a network. Live objects can be composed in a type-safe manner to build sophisticated distributed applications using a simple, intuitive drag and drop interface, very often without writing any code or having to understand the intricacies of the underlying distributed algorithms.
1 Motivation
It has become common to build applications in a component-oriented manner, composing reusable building blocks by binding strongly-typed interfaces. At runtime, an underlying object-oriented managed environment, such as Java/J2EE or .NET provides further checking and support. The paradigm has numerous benefits: it promotes clean, modular architectures, facilitates extensions, enables collaborative development and code reuse, and by making contracts between components explicit and their code more isolated, reduces the risk of bugs resulting from badly documented or implicit assumptions such as cross-component behavior or side effects.
Unfortunately, distributed systems developers are only able to exploit these tools in limited ways, typically wedded to client-server programming styles. Moreover, the most widely used technologies can be awkward and inflexible. For example, a developer uses different methods to access a system depending on whether it is hosted on a single remote server [6], cloned for load-balancing on a cluster [37], or using state machine replication [52]. Yet even as the available tools have standardized on these limited options, the research community is creating a wave of powerful new technologies that includes peer-to-peer and gossip protocols, multicast with various levels of consistency, ordering and timing, Byzantine state replication, distributed hash tables, credential management services, naming services, content distribution networks, etc.
Our goal is to break through this barrier by treating protocols as components in the same sense as in .NET or COM. We propose a technology in which application components and protocols are unified within a single object-oriented paradigm. Our “live distributed objects” represent running instances of distributed protocols, but they have types and support composition, much like “ordinary” objects. While ours is certainly not the first approach to unify distributed protocols with object-oriented environments, we innovate in ways that make the solution uniquely powerful:
· We leverage the type system without being language-specific. Our platform offers mechanisms such as reflection and dynamic type checking, previously seen only in systems closely tied to an underlying language, such as Smalltalk, Java, ML or IOA. In our interactive GUI, type-checking prevents users from dropping objects in inappropriately. Down the road, we’ll use type checking to ensure that replicated application objects use a protocol with sufficiently strong properties.
· It can be incrementally deployed, and supports legacy applications, including Excel spreadsheets, Oracle databases, and web services. For example, we can import data from a database, multicast it, and export it back into a set of desktop spreadsheets.
· Our object-oriented embedding can support any distributed protocol as a reusable component. Existing systems are protocol-agnostic only in the limited sense that users can choose among several different protocols to implement communication. For us, protocols are objects; a small shift in perspective with broad implications.
· The approach extends from the UI to the hardware level, whereas prior systems focused on one class of application objects, e.g. shared data structures or UI components. Jini has a vision similar to ours, but is tightly bound to the client-server paradigm, whereas our model is focused on distributed multi-party protocols.
· We support composition of behavioral protocol types. Prior composition toolkits either lacked types, or used a limited form of typing, where the protocol type was the type of the implementing class, and composition was achieved via inheritance.
· Our model is replication-centric. Although many live objects don’t replicate state, the handling of replication and scalability sets our solution apart from prior ones. We’re able to support various replication (multicast) models, and to express this in a type system.
· Our system may be the first drag and drop tool for type-safe protocol composition. Drag and drop mechanisms are easy to use and yet can support sophisticated applications. For many applications, no new code is needed at all. Prior systems (including some from which we took inspiration, such as Ensemble [33], BAST [20], x-Kernel [45], and I/O automata [36]) were programmer-intensive.
Although the current system is quite usable, live objects raise a number of questions, only some of which have been addressed. The technology requires a scalable multicast layer capable of supporting very large groups, and in which a single node can join large numbers of object-groups. In work reported elsewhere, we describe Quicksilver, a high-performance, scalable communication layer that achieves these goals [46,47,48]. We’re also collaborating with a group at INRIA/IRISA on a gossip-based infrastructure compatible with live objects; we expect this to be useful for discovering and tracking system configuration information. Looking further out, we’re extending Quicksilver to support a range of reliability models (expressed in a new protocol scripting language [47]), and are implementing a new security architecture based on reflection. We also have ideas for WAN and mobile applications, debugging, performance tuning, system management, and object state persistence. However, all of these questions lie beyond the scope of the present paper.
2 Prior Work
While we believe our work to be innovative in the ways just described, we’re not the first to integrate the object-oriented and distributed programming models.
There are many language abstractions for distributed protocols, including remote objects [17, 20], fault-tolerant objects [24], multicast objects [19], asynchronous collections [9], tuple spaces [6, 38], and replicated objects driven by multicast [25, 37] or two-phase commit [34]. None matches the requirements described above. First, these abstractions are all specialized to support specific protocols. For example, asynchronous collections cannot easily be used to express two-phase commit or leader election. Second, most lack the notion of a distributed type, and in those that do, this notion is shallow, e.g. the type of a multicast object [19] is determined by the type of transmitted events, and the type of an asynchronous collection [9] is the type of the implementing class. The former definition can’t convey information about subtle behaviors of protocols such as virtual synchrony [5], while the latter severely restricts reusability. Finally, most lack support for composition.
The idea of defining object types in terms of their behaviors is not new [55]. CSP [24] and π-calculus [41] were some of the first protocol specifications, and these early process calculi serve as a basis for recent specification efforts, such as BPEL [3], SSDL [49], and WSCL [4]. As recently noted [19], the weakness of process calculi, and specifications based on them, is that they can’t express the semantics of replication or the behavior of protocols such as consensus in a clean way. For example, while BPEL is clearly strong enough to express business processes, the language defines protocols in terms of sets of participants fixed at the outset, and can’t model dynamic join or leave events. It would be very hard to express replication properties, such as “once any group member does X, eventually all operational members do too” [12].
On the other hand, while state-based approaches such as I/O automata [36], CFSM [7], interface automata [1], and others [18] are very expressive, they combine functional descriptions of protocol behaviors with the specifics of their implementations expressed through state transitions. This is useful in correctness proofs, but it may be a weakness in the context of a type system. Two protocols implemented using different data structures and states can exhibit the same external behavior, e.g. “messages are totally ordered and delivered atomically with respect to failures”. We believe that protocols that behave equivalently should be considered to have the same distributed type; state transition representations can easily obscure such relationships [27].
Live objects support an extensible style of formal behavioral specifications for group and multicast protocols [2, 12, 22, 26]. As one composes protocols, a constructive distributed type system is obtained. The type checking mechanism is itself componentized, and can be extended by developers.
The idea of building protocols from simpler components dates to the x-Kernel [45] and to systems like Ensemble [33], which constructed replication protocols from microprotocols. Among such systems, BAST [20] is closest to ours in terms of the diversity of protocols it can express, but lacks a behavioral notion of a protocol type: protocol types in BAST are determined by the types of the implementing classes, and composition is achieved by inheritance. The creators of BAST observed that in retrospect, inheritance wasn’t the right mechanism for this task. We’ve drawn lessons from these experiences and created a model in which inheritance isn’t used at all: we treat protocols as black boxes and connect them with typed event channels in a visual designer. Our protocol objects interact via events, much as in Smalltalk [21].
Jini [57], the widely used Java-based platform in which clients access services by dynamically loading proxy code, is highly relevant prior work. The strongest contrast is that Jini has a pervasive client-server bias, making it very hard to express object replication, particularly in applications that use strong consistency or (at the other extreme) peer-to-peer protocols.
This client-server bias is visible in many ways. First, Jini lacks a rigorous notion of a group [43], and it is hard to implement consistency across a set of group members, state replication within the group, coordination, leader-election, etc. Jini's lookup, join, and discovery specifications lack membership views (needed to assign tasks to group members) and synchronized state transfer (used to initialize new group members). Moreover, Jini doesn’t guarantee consistent failure detection. Thus, while services in Jini can be grouped, the mechanism lacks expressive power to facilitate building systems that use stronger forms of replication. Additionally, abstractions such as notification and transactional protocols can’t be directly modeled as objects in Jini. Finally, Jini lacks distributed types and protocol composition mechanisms.
Live objects are replication-centric, with a strong notion of protocol types and composition. This makes live objects particularly appropriate for building applications in which users collaborate, share content, or engage in other kinds of peer-to-peer behaviors, (obviously we can also support traditional non-replicated and client-server behaviors). Complex protocols can be modeled as objects, in a manner that separates behavior of the protocol from its implementation.
Many of these same issues distinguish our work from WS-* standards. Elsewhere [48], we discuss issues that arise if one tries to use WS-Notification or WS-Eventing to implement live objects. We concluded that the relevant WS-* standards are tightly bound to specific protocol implementations; as written, they cannot accommodate commercially important protocols such as peer-to-peer video streaming, BitTorrent, or Byzantine replication. We’ve proposed an extended WS-based eventing standard matched to the work described here, and able to overcome this problem [48].
JXTA [57] is probably the most sophisticated existing collaboration technology for peer-to-peer systems, but it doesn’t support stronger replication and consistency models. While JXTA does have notions such as a group and a membership view, members can have inconsistent views. Researchers have struggled to layer reliable multicast on these mechanisms [35]. Groupware toolkits, such as Croquet [53], Groove [39], and group communication [5] toolkits all support replication, and some support strong forms of consistency. However, unlike Jini, JXTA and our work, none of these is positioned as a general-purpose interoperability platform.
3.1 Objects and Their Interactions
A live distributed object (or live object) is an instance of a distributed protocol: programming logic executed by a set of components that may reside on different nodes and communicate by sending messages over the network. For flexibility, we won’t assume that the machines running the protocol “know” about one-another or that they share any common state. Thus, a live object could be a Byzantine fault-tolerant replicated state machine, but it could also be an entity with purely local state, one that uses gossip to share data, or an IP multicast channel.
Live objects have behavioral types. Suppose that object A logs messages on the nodes where it runs, using a reliable, totally ordered multicast to ensure consistency between replicas. Object B might offer the same functionality, but be implemented differently, perhaps using a gossip protocol. As long as A and B offer the same interfaces and equivalent properties (consistency, reliability, etc), we consider A and B to be implementations of the same type. The concept of behavioral equivalence is the key here; we define it more carefully in section 3.2.
When node Y executes live object X, we’ll say that a proxy of live object X is running on Y. Thus, a live object is executed by the group of its proxies (Figure 1). A proxy is a functional part of the object running on a node. When two objects have proxies on overlapping sets of nodes, their respective proxies may interact. We can think of the live objects as interacting through their proxies.
Figure 1. To access a live object (protocol), a node starts a proxy: a software component that runs the protocol on the node, and may communicate with proxies on other nodes by sending messages over the network. On a given node, proxies for different objects communicate via endpoints: strongly-typed, bidirectional event channels.
A reference to a live object X is a complete set of instructions for constructing and configuring a proxy of X on a node. Thus, when node Y wants to access live object X, node Y uses a reference to X as a recipe with which it can create a new proxy for X that will run locally on Y. The proxy then executes the protocol associated with X. For example, it might seek out other proxies for X, transfer the current distributed state from them, and connect itself to a multicast channel to receive updates. Unlike proxies, which can have state, references are just passive, stateless, portable recipes.
The instructions in a reference must be complete, but need not be self-contained. Some of their parts can be stored inside online repositories, from which they need to be downloaded. These repositories are themselves live objects, referenced by the objects that use them. Thus, given a reference, a node can dereference it without prior “knowledge” of the protocol. An exception is thrown if dereferencing fails (for example, if a repository containing a part of the reference is unavailable).
We model proxies in a manner reminiscent of I/O automata. A proxy runs in a virtual context consisting of a set of endpoints: strongly-typed bidirectional event channels, through which the proxy can communicate with other software on the same node (Figure 1). Unlike in I/O automata, a proxy can use external resources, such as local network connections, clocks, or the CPU. These interactions are not expressed in our model and they are not limited in any way. However, interactions of a live object’s proxy with any other component of the distributed system must be channeled through the proxy’s endpoints.
All proxies of the same live object run that live object’s code. Unlike in state machines [37, 52], we need not assume that proxies run in synchrony, in a deterministic manner, or that their internal states are identical. We do assume that each proxy of a live object X interacts with other components of the distributed system using the same set of endpoints, which must be specified as part of X’s type. To avoid ambiguity, we sometimes use the term instance of endpoint E at proxy P to explicitly refer to a running event channel E, physically connected to and used by P.
Because our model is designed to facilitate component integration, we shall adopt a somewhat radical perspective, in which the entire system, all applications and infrastructure are composed of live objects. Accordingly, endpoints of a live object’s proxy will be connected to endpoints exposed by proxies of other live objects running on the same node (Figure 2). When proxies of two different objects X and Y are connected through their endpoints on a certain node Z, we’ll say that X and Y are connected on Z.
Figure 2. Applications in our model are composed of interconnected live objects. Objects are “connected” if endpoints of a pair of their proxies are connected. Connected objects can affect one-another by having their proxies exchange events through endpoints. A single object can be connected to multiple other objects. Here, a reliable multicast object r is simultaneously connected to an unreliable multicast object u, a membership object m, and an application object a. The same object can be accessed by different machines in different ways. For example, m is used in two contexts: by the multicast object r, and by replicas of a membership service. The latter employs a replicated state machine s, which persists its state through a storage object p.
Example (a). Consider a distributed collaboration tool that uses reliable multicast to propagate updates between users (Figure 2). Let a be an application object in this system that represents a collaboratively edited document. Proxies of a have a graphical user interface, through which users can see the document and submit updates. Updates are disseminated to other users over a reliable multicast protocol, so that everyone can see the same contents. The system is designed in a modular way, so instead of linking the UI code with a proprietary multicast library, the document object a defines a typed endpoint reliable_channel_client, with which its proxies can submit updates to a reliable multicast protocol (event send) and receive updates submitted by other proxies and propagated using multicast (event receive). Multicasting can then be implemented by a separate object r, which has a matching endpoint reliable channel. Proxies of a and r on all nodes are connected through their matching endpoints. n
Similarly, object r may be structured in a modular way: rather than being a single monolithic protocol, r could internally use object u for dissemination and object m for membership tracking [12]. Additional endpoints unreliable channel and membership would serve as contracts between r and its internal parts u and m.
Figure 2 illustrates several features of our model. First, a pair of endpoints can be connected multiple times: there are multiple connections between different instances of the reliable channel endpoint of object r and the reliable_channel_client endpoint of a, one connection on each node where a runs. Since objects are distributed, so are the control and data flows that connect them. If different proxies of r were to interact with proxies of a in an uncoordinated manner, this might be an issue. To prevent this, each endpoint has a type, which constrains the patterns of events that can pass through different instances of the endpoint. These types could specify ordering, security, fault-tolerance or other properties. The live objects runtime won’t permit connections between a and r, unless their endpoint types declare the needed properties.
A single object could also define multiple endpoints. One case when this occurs is when the protocol involves different roles. For example, the membership object m has two endpoints, for clients and for service replicas. The role of the proxy in the protocol depends on which endpoint is connected. In this sense, endpoints are like interfaces in object-oriented languages, giving access to a subset of the object’s functionality. Another similarity between endpoints and interfaces is that both serve as contracts and isolate the object’s implementation details from the applications using it. We also use multiple endpoints in object r, proxies of which require two kinds of external functionality: an unreliable multicast, and a membership service. Both are obligatory: r cannot be activated on a platform unless both endpoints can be connected.
Earlier, we commented that not all live objects replicate their state. We see the latter in the case of the persistent store p. Its proxies present the same type of endpoint to the state machine s, but each uses a different log file and has its own state.
Our model promotes reusability by isolating objects from other parts of the system via endpoints that represent strongly typed contracts. If an object relies upon external functionality, it defines a separate endpoint by which it gains access to that functionality, and specifies any assumptions about the entity it may be connected to by encoding them in the endpoint type. This allows substantial flexibility. For example, object u in our example could use IP multicast, an overlay, or BitTorrent, and as long as the endpoint that u exposes to r is the same, r should work correctly with all these implementations. Of course this is conditional upon the fact that the endpoint type describes all the relevant assumptions r makes about u, and that u does implement all of the declared properties.
3.2 Defining Distributed Types
The preceding section introduced endpoint types, as a way to define contracts between objects. We now define them formally and give examples of how typing can be used to express reliability, security, fault-tolerance, and real time properties of objects.
Formally, the type Θ of a live object is a tuple of the form Θ = (E, C, C'). E in this definition is a set of named endpoints, E = {(n1, τ1), (n2, τ2), …, (nk, τk)}, where ni is the name and τi is the type of the ith endpoint. C and C' represent sets of constraints describing security, reliability, and other characteristics of the object (C), and of its environment (C'). C models constraints provided by the object, such as semantics of the protocol: guarantees that the object’s code delivers to other objects connected to it. C' models constraints required, which are prerequisites for correct operation of the object’s code. Constraints can be described in any formalism that captures aspects of object and environment behavior in terms of endpoints and event patterns. Rather than trying to invent a new, powerful formalism that subsumes all the existing ones, we build on the concepts of aspect-oriented programming [28], and we define C to be a finite function from some set A of aspects to predicates in the corresponding formalisms. For example, constraints C = {(a1, φ1), (a2, φ2), …, (am, φm)} would state that in formalism a1 the object’s behavior satisfies formula φ1, and so on. We’ll give examples of various practically useful formalisms and constraints later in this section.
Type τ of an endpoint is a tuple of the form τ = (I, O, C, C'). I is a set of incoming events that a proxy owning the endpoint can receive from some other proxy, O is a set of outgoing events that the proxy can send over this endpoint, and C and C' represent constraints provided and required by this endpoint, defined similarly to constraints of the object, but expressed in terms of event patterns, not in terms of endpoints (for example, an endpoint could have an event of type time, and with a constraint that time advances monotonically in successive events). Each of the sets I and O is a collection of named events of the form E = {(n1, ε1), (n2, ε2), …, (nk, εk)}, where ni is event name and εi is its type. Event types can be value types of the underlying type system, such as .NET or Java primitive types and structures, or types described by WSDL [13] etc., but not arbitrary object references or addresses in memory. We assume that events are serializable and can be transmitted across the network or process boundaries. References to live objects are also serializable, hence they can also be passed inside events. The subtyping relation on the event types is inherited from the underlying type system.
The purpose of creating endpoints is to connect them to other, matching endpoints, as described in Section 3.1 and illustrated on Figure 2. Connect is the only operation possible on endpoints. We say that endpoint types τ1 and τ2 match, denoted τ1 µ τ2, when the following two conditions hold.
1.For each output event n of type ε of either endpoint, its counterpart must have an input event with the same name n, and with either type ε, or some supertype of ε. This guarantees that all events can be delivered between the two connected proxies.
2.The provided constraints of each of the endpoints must imply (be no weaker than) the required constraints of the other. This ensures that the endpoints mutually satisfy each other’s requirements.
Formally, for τ1 = (I1, O1, C1, C1') and τ2 = (I2, O2, C2, C2') we define:
|
τ1 µ τ2 Û O1 ®* I2 Ù O2 ®* I1 Ù C1 Þ* C2' Ù C2 Þ* C1'. |
(1) |
Relation ®* between two sets of named events expresses the fact that events from the first can be understood as events from the second. Formally, we express it as follows:
|
E ®* E' Û " (n, e)ÎE $ (n, e′)ÎE' such that e ≤ e′. |
(2) |
Operator “≤” on types always represents the relation of subtyping in this paper.
Relation Þ* between two sets of constraints expresses the fact that the constraints in the first set are no weaker than constraints in the second. Formally, we write this as:
|
C Þ* C' Û " (a, φ′)ÎC′ $ (a, φ)ÎC such that φ Þa φ'. |
(3) |
Relation Þa is simply a logical consequence in formalism a. Intuitively, this definition states that if C' defines a constraint defined in some formalism, then C must define a constraint that is no weaker than that, in the same formalism. For example, if C' defines some reliability constraint expressed in temporal logic, then C must define an equivalent or stronger constraint, also in temporal logic, in order for C Þ* C' to hold.
For a pair of endpoint types τ1 and τ2, the former is a subtype of the latter if it can be used in any context in which the latter can be used. Since the only possible operation on an endpoint is connecting it to another, matching one, hence τ1 ≤ τ2 holds iff τ1 matches every endpoint that τ2 matches, i.e. τ1 ≤ τ2 iff "τ′ (τ2 µ τ′) Þ (τ1 µ τ′), which after expanding the definition of “µ” can be formally expressed as follows:
|
τ1 ≤ τ2 Û O1 ®* O2 Ù I2 ®* I1 Ù C1 Þ* C2 Ù C2′ Þ* C1′. |
(4) |
Intuitively, τ1 ≤ τ2 if (a) τ1 defines no more output events and no fewer input events than τ2, (b) the types of output events of τ1 are subtypes and the types of input events of τ1 are supertypes of the corresponding events of τ2, and (c) the provided constraints of τ1 are no weaker and the required constraints of τ1 are no stronger than those of τ2.
Subtyping for live object types is defined in a similar manner. Type Θ1 is a subtype of Θ2, denoted Θ1 ≤ Θ2, when Θ1 can replace Θ2. Since the only thing that one can do with a live object is connect it to another object through its endpoints, this boils down to whether Θ1 defines all the endpoints that Θ2 defines, and whether the types of these endpoints are no less specific, and whether Θ1 guarantees no less and expects no more than Θ2. Formally, for two types Θ1 = (E1, C1, C1′) and Θ2 = (E2, C2, C2′), we define:
|
Θ1 ≤ Θ2 Û E1 ≤* E2 Ù C1 Þ* C2 Ù C2′ Þ* C1′. |
(5) |
Relation ≤* between sets of named endpoints used above is defined as follows:
|
E ≤* E' Û " (n, τ′)ÎE′ $ (n, τ)ÎE such that τ ≤ τ′. |
(6) |
The use of types in our platform is limited to checking whether the declared object contracts are compatible, to ensure that the use of objects corresponds to the developer’s intentions. The live objects platform performs the following checks at runtime:
1.When a reference to an object of type Θ is passed as a value of a parameter that is expected to be a reference to an object of type Θ', the platform verifies that Θ ≤ Θ'.
2.When an endpoint of type τ is to be connected to an endpoint of type τ', either programmatically or during the construction of composite objects described in Section 4.2, the platform verifies that the two endpoints are compatible i.e. that τ µ τ'.
We believe that in practice, this limited form of type safety is sufficient for most uses. For provable security, the runtime could be made to verify that live object’s code implements the declared type prior to execution. Techniques such as proof-carrying code [44] and domain-specific languages with limited expressive power could facilitate this.
3.3 Constraint Formalisms
We conclude this section with a discussion of different formalisms that can be used to express the constraints in the definition of objects and endpoints. The issue is subtle because on the one hand, a type system won’t be very helpful if it has nothing to check, but on the other hand, there are a great variety of ways to specify protocol properties. It isn’t much of an exaggeration to suggest that every protocol of interest brings its own descriptive formalism to the table! As noted earlier, many prior systems have effectively selected a single formalism, perhaps by defining types through inheritance. Yet when we consider protocols that might include time-critical multicast, IPTV, atomic broadcast, Byzantine agreement, transactions, secure key replication, and many others, it becomes clear that no existing formalism could possibly cover the full range of options.
A further issue is the incompleteness of many specifications, in a purely formal sense. For example, one popular formalism is temporal logic [22,12]. Here, we assume a global time and a set of locations, and a function that maps from time to events that occur at those locations. In the context of endpoint constraints, we can think of instances of the endpoint as locations, and the endpoint’s incoming and outgoing events, and explicit connect/disconnect events, as the events of the temporal logic. Constraints would be expressed as formulas over these events, identifying the legal event sequences within the (infinite) set of possible system histories.
Example (b). Consider the reliable channel endpoint, exposed by the reliable channel r in the example in Section 3.1. The endpoint’s type might define one incoming event send(m) and one outgoing event receive(m), parameterized by message body m. Constraints provided by the channel object r might include a temporal logic formula stating that if event receive(m) is delivered by r through some of the instances of the endpoint sooner than receive(m′), then for any other instance of the endpoint, if both events are delivered, they are delivered in the same sequence. n
Example (b) illustrates a safety property of a type for which temporal logic is especially convenient. Chockler et. al. use temporal logic to specify a range of reliable multicast protocols in [12]. However, the FLP impossibility result establishes that these protocols cannot guarantee liveness in traditional networks. Thus, while we can express a liveness constraint in such a logic, no protocol could achieve it – in effect, such a protocol type would be useless in real systems!
Temporal logic is just one of many useful formalisms. In our work on a security architecture, still underway, we’re looking into using a variant of the BAN logic [9] to define security properties provided by live objects or expected from their environment. Real-time and performance guarantees are conveniently expressed as probabilistic guarantees on event occurrences, e.g. in terms of predicates such as “at least p % of the time, receive(m) occurs at all endpoint instances at most t seconds following send(m),” or “at least p % of the time, receive(m) occurs at all different endpoint instances in a time window of at most t seconds”.
Yet another useful formalism would be a version of temporal logic that talks about the number of instances of different endpoints in time. For example, constraints of the sort “at most one instance of the publisher endpoint may be connected at any given time” could describe single-writer semantics or similar assumptions made by the protocol designer. Constraints of this sort could also express fault-tolerance properties, e.g. define the minimum number of proxies to maintain a certain replication level etc.
In general, with formalisms like those listed above, type-checking might involve a theorem prover, and hence may not always be practical. In practice, however, the majority of object and endpoint types would choose from a relatively small set of standard constraints, such as best-effort, virtually-synchronous, transactional, or atomic dissemination, total ordering of events etc. Predicates that represent common constraints could be indexed, and stored as macros in a standard library of such predicates, and the object and endpoint types would simply list such macros. The runtime would perform type-checking by comparing such lists, and using cached known facts, such as that a virtually synchronous channel is also best-effort reliable etc. By taking advantage of late binding and reflection, features of .NET and of most Java platforms, it is easy to make these mechanisms extensible in a “plug and play” manner. This will allow developers to introduce additional formalisms down the road.
3.4 Group Types
Readers familiar with group communication [5,11] may be concerned that although our model is fundamentally about creating and working with groups of entities (live object proxies), the type system itself lacks a rigorous notion of a group. This actually makes our model simpler and more generic, without preventing us from expressing group properties. For example, to model a virtually synchronous group, we can define a pair of endpoints channel and membership, and specify constraints on the occurrences of events on the two endpoints, as in group communication specifications [12]. Within groups of endpoints, one can use temporal logic formulas with operators such as everywhere and everywhere within a membership view, much as in [2,12,22]. To bind to such a group an object would define two matching endpoints. This approach has the advantage of generality: we can potentially express a range of group semantics.
4 Language Embeddings and Support for Composition
4.1 Language Embeddings
Our model has a good fit with modern object-oriented programming languages. There are two aspects of this embedding. On one hand, live object code can be written in a language like Java and C# (we will demonstrate this in Section 4.2). On the other hand, live objects, proxies, endpoints, and connections between them are first-class entities that can be used within C# or Java code. Their distributed types build upon and extend the set of non-distributed types in the underlying managed environment. In this section, we’ll discuss each of the new programming language entities we introduce: references to live objects, references to proxies, references to endpoint instances, and references to connections between endpoints. An example of their use is shown in Code 1. We will conclude this section with a discussion of two more advanced mechanisms, template object references and casting operator extensions.
01 void ReceiveObject(ref<liveobject> ref_object) // code of an event handler
02 {
03 if (referenced_type(ref_object) is SharedFolder)
04 {
05 ref<SharedFolder> ref_folder := (ref<SharedFolder>) ref_object;
06 SharedFolder folder := dereference(ref_folder); // creates a proxy
07 external<FolderClient> folder_ep := endpoint(folder, “folder”);
08 internal<FolderClient> my_ep := new_endpoint<FolderClient>();
09 my_ep.AddedElement += ...; // here’s a code that registers an event handler
10 connection my_connection := connect(folder_ep, my_ep);
11 // some code to store the newly created proxy and endpoint connection references
12 }
13 }
Code 1. An example piece of code in a language similar to C#, but with a simplified syntax for legibility. Here, “ReceiveObject” is a handler of an incoming event of a live object proxy. The event is parameterized by a live object reference “ref_object”. If the reference is to a shared folder, the code launches a new proxy to connect to the folder’s protocol and attaches a handler to event “AddedElement” generated by this protocol, in order to monitor this folder’s contents.
A. References to Live Objects. Operations that can be performed on these references include reflection (inspecting the referenced object’s type), casting, and dereferencing (the example uses are shown in Code 1, in lines 03, 05, and 06 accordingly). Dereferencing results in the local runtime launching a new proxy of the referenced object (recall from Section 3.1 that references include complete instructions for how to do this). The proxy starts executing immediately, but its endpoints are disconnected A reference to the new proxy is returned to the caller (in our example it is assigned to a local variable folder). This reference controls the proxy’s lifetime. When it is discarded and garbage collected, the runtime disconnects all of the proxy’s endpoints and terminates it. To prevent this from happening, in our example code we must store the proxy reference before exiting (we would do so in line 11).
Whereas a proxy must have a reference to it to remain active, a reference to a live object is just a pointer to a recipe for constructing a proxy for that object, and can be discarded at any time. An important property of object references is that they are serializable, and may be passed across the network or process boundaries between proxies of the same or even different live objects, as well as stored on in a file etc. The reference can be dereferenced anywhere in the network, always producing a functionally equivalent proxy – assuming, of course, that the node on which this occurs is capable of running the proxy. In an ideal world, the environmental constraints would permit us to determine whether a proxy actually can be instantiated in a given setting, but the world is obviously not ideal. Determining whether a live object can be dereferenced in a given setting, without actually doing so, is probably not possible.
The types of live object references are based on the types of live objects, which we will define formally below. To avoid ambiguity, if Θ is a live object type, and x is a reference to an object of type Θ, we will write ref<Θ> to refer to the type of entity x.
The semantics of casting live object references is similar to that for regular objects. Recall that if a regular reference of type IFoo points to an object that implement IBar, we can cast the reference to IBar even if IFoo is not a subtype of IBar, and while as a result the type of the reference will change, the actual referenced object will not. In a similar manner, casting a live object reference of type ref<Θ> to some ref<Θ′> produces a reference that has a different type, and yet dereferencing either of these references, the original one or the one obtained by casting, result in the local runtime creating the same proxy, running the same code, with the same endpoints. A reference can be cast to ref<Θ> for as long as the actual type of the live object is a subtype of Θ.
B. References to Proxies. The type of a proxy reference is simply the type of the object it runs, i.e. if the object is of type Θ, references to its proxies are of type Θ. Proxy references can be type cast just like live object references. One difference between the two constructs is that proxy references are local and can’t be serialized, sent, or stored. Another difference is that they have the notion of a lifetime, and can be disposed or garbage collected. Discarding a proxy reference destroys the locally running proxy, as explained earlier, and is like assigning null to a regular object reference in a language like Java. The live object is not actually destroyed, since other proxies may still be running, but if all proxy references are discarded (and proxies destroyed), the protocol ceases to run, as if it were automatically garbage collected.
Besides disposing, the only operation that can be performed on a proxy reference is accessing the proxy endpoints for the purpose of connecting to the proxy. An example of this is seen in line 07, where we request the proxy of the shared folder object to return a reference to its local instance of the endpoint named “folder”.
C. References to Endpoint Instances. There are two types of references to endpoint instances, external and internal. An external endpoint reference is obtained by enumerating endpoints of a proxy through the proxy reference, as shown in line 07. The only operation that can be performed with an external reference is to connect it to a single other, matching endpoint (line 10). After connecting successfully, the runtime returns a connection reference that controls the connection’s lifetime. If this reference is disposed, the two connected endpoints are disconnected, and the proxies that own both endpoints are notified by sending explicit disconnect events.
An internal endpoint reference is returned when a new endpoint is programmatically created using operator new (line 08). This is typically done in the constructor code of a proxy. Each proxy must create an instance of each of the object’s endpoints in order to be able to communicate with its environment. The proxy stores the internal references of each of its endpoints for private use, and provides external references to the external code per request, when its endpoints are being enumerated. Internal references are also created when a proxy needs to dynamically create a new endpoint, e.g. to interact with a proxy of some subordinate object that it has dynamically instantiated.
An internal reference is a subtype of an external reference. Besides connecting it to other endpoints, it also provides a “portal” through which a proxy that created it can send or receive events to other connected proxies. Sending is done simply by method calls, and receiving by registering event callbacks (line 09).
An important difference between external and internal endpoint references is that the former could be serialized, passed across the network and process boundaries, and then connected to a matching endpoint in the target location. The runtime can implement this e.g. by establishing a TCP connection to pass events back and forth between proxies communicating this way. This is possible because events are serializable.
Internal endpoint references are not serializable. This is crucial, for it provides isolation. Since any interaction between objects must pass through endpoints, and events exchanged over endpoints must be serializable, this ensures that an internal endpoint reference created by a proxy cannot be passed to other objects or even to other proxies of the same object. Only the proxy that created an endpoint has access to its portal functionality of an endpoint, and can send or receive events with it.
D. References to Connections. Connection references control the lifetime of connections. Besides disposing, the only functionality they offer is to register callbacks, to be invoked upon disconnection. These references are not strongly typed. They may be created either programmatically (as in line 10 in Code 1), or by the runtime during the construction of a composite proxy. The latter is discussed in detail in Section 4.2.
E. Template Object References. Template references are similar to generics in C# or templates in C++. Templates are parameterized descriptions of proxies; when dereferencing them, their parameters must be assigned values. Template types do not support subtyping, i.e. references of template types cannot be cast or assigned to references of other types. The only operation allowed on such references is conversion to non-template references by assigning their parameters, as described in Section 4.2.
Template object references can be parameterized by other types and by values. The types used as parameters can be object, endpoint, or event types. Values used as parameters must be of serializable types, just like events, but otherwise can be anything, including string and int values, live object references, external endpoint references etc.
Example (c). A channel object template can be parameterized by the type of messages that can be transmitted over the channel. Hence, one can e.g. define a template of a reliable multicast stream and instantiate it to a reliable multicast stream of video frames. Similarly, one can define a template dissemination protocol based on IP multicast, parameterized with the actual IP multicast address to use. A template shared folder containing live objects could be parameterized by the type of objects that can be stored in the folder and the reference to the replication object it uses internally. n
F. Casting Operator Extensions. This is a programmable reflection mechanism. Recall that in C# and C++, one can often cast values to types they don’t derive from. For example, one can assign an integer value to a floating-point type. Conversion code is then automatically generated by the runtime, and injected into this assignment. One can define custom casting operators for the runtime to use in such situations. Our model also supports this feature. If an external endpoint or an object reference is cast to a mismatching reference type, the runtime can try to generate a suitable wrapper.
Example (d). Consider an application designed to use encrypted communication. The application has a user interface object u exposing a channel endpoint, which it would like to connect to a matching endpoint of an encrypted channel object. But, suppose that the application has a reference to a channel object c that is not encrypted, and that exposes a channel endpoint of type lacking the required security constraints. When the application tries to connect the endpoints of u and c, normally the operation would fail with a type mismatch exception. However, if the channel endpoint of c can be made compatible with the endpoint of u by injecting encryption code into the connection, the compiler or the runtime might generate such wrapper code instead. Notice that proxies for this wrapper would run on all nodes where the channel proxy runs, and hence could implement fairly sophisticated functionality. In particular, they could implement an algorithm for secure group key replication. In effect, we are able to wrap the entire distributed object: an elegant example of the power of the model. n
The same can be done for object references. While casting a reference, the runtime may return a description of a composite reference that consists of the old proxy code, plus the extra wrapper, to run side by side (we discuss composite references in Section 4.2). In addition to encryption or decryption, this technique could be used to automatically inject buffering code, code that translates between push and pull interface, code that persists or orders events, automatically converts event data types, and so on.
Currently, our platform uses casting only to address certain kinds of binary incompatibilities, as explained in Section 5.2. In future work, we plan to extend the platform to support more sophisticated uses of casting, e.g. as in the example above, and define rules for choosing casting operators when more that one is available.
4.2 Construction and Composition
As noted in Section 4.1, a live object exists if references to it exist, and it runs if any proxies constructed from these references are active. Creating new objects thus boils down to creating references, which are then passed around and dereferenced to create running applications. Object references are hierarchical: references to complex objects are constructed from references to simpler objects, plus logic to “glue” them together. The construction can use four patterns, for constructing composite, external, parameterized, and primitive objects. We shall now discuss these, illustrating them with an example object reference that uses each of these patterns, shown in Code 2.
01 parameterized object // an object based on a parameterized template
02 using template primitive object 3 // the id of a “shared document” template
03 {
04 parameter "Channel" :
05 composite object // a complex object built from multiple component objects
06 {
07 component "DisseminationObject" :
08 external object "MyChannel" as Channel
09 from external object "QuickSilver" as Folder<Id, Channel>
10 from primitive object 2 // the id of a predefined “registry” object
11 component "ReliabilityObject" :
12 … // specification of some loss recovery object, omitted for brevity
13 connection // an internal connection between a pair of component endpoints
14 endpoint "UnreliableChannel" of "DisseminationObject"
15 endpoint "UnreliableChannel" of "ReliabilityObject"
16 export // endpoints of the components to be exposed by the composite object
17 endpoint "ReliableChannel" of "ReliabilityObject"
18 }
19 }
Code 2. An example live object reference, based on a shared document template, parameterized by a reliable communication channel. The channel is composed of a dissemination object and a reliability object, connected to each other via their “UnreliableChannel” endpoints, much like r and u in Figure 2. The “ReliableChannel” endpoint of the reliability object is exposed by the channel. The dissemination object reference is to be found as an object named “MyChannel”, of type “Channel”, in an online repository (“Id” and “Channel” are predefined types). The reference to the repository is to be found, as an object named “QuickSilver”, of type “Folder”, i.e. containing channels, in another online repository, the “registry” object (see Section 4.2).
A. Composite References. A composite object consists of multiple internal objects, running side by side. When such an object is instantiated, the proxies of the internal objects run on the same nodes (like objects r and u in Figure 2). A composite proxy thus consists of multiple embedded proxies, one for each of the internal objects. A composite reference contains embedded references for each of the internal proxies, plus the logic that glues them together. In the example reference shown in lines 05 to 18 in Code 2, there is a separate section “component name : reference” for each of the embedded objects, specifying its internal name and reference. This is followed by a section of the form “connection endpoint1 endpoint2”, for each internal connection. Finally, for every endpoint of some embedded internal object that is to be exposed by the composite object as its own, there is a separate section “export endpoint”.
When a proxy is constructed from a composite reference, the references to any internal proxies and connections are kept by the composite proxy, and discarded when the composite proxy is disposed of (Figure 3). The lifetimes of all internal proxies are thus connected to the lifetime of the composite. Embedded objects and their proxies thus play the role analogous to member fields of a regular object.
Figure 3. A live object class diagram for the composite object in Code 2 (left) and the structure of the composite proxy (right). When constructing a composite proxy, the runtime automatically constructs all the internal proxies and the internal connections between them, and stores their references in the composite proxy. Embedded proxies and connections are destroyed together with the composite proxy. The latter can expose some of the internal endpoints as its own.<