page 2  (12 pages)
to previous section1
3to next section

distinguishes between variables, records, procedures, cells and ports. Cells are used to implement concurrent object state. Ports are used to implement many-to-one and manyto-many channels. Each of these entities has a network protocol that is used whenever a basic operation is performed on it. The network protocols are designed to preserve language semantics while providing a simple model for the communication patterns.

1.2 Oz as the foundation

The Oz language appears to the programmer as a concurrent object-oriented language that is state-aware and has dataflow synchronization [8].1 In a broader context, Oz is a successful attempt to integrate several programming paradigms (including object-oriented, functional, and constraint logic) into a simple model [22]. This model allows to understand various forms of computation as facets of a single phenomenon. This increases the range of problems that can easily be cast into the language [23]. Oz has a fully defined formal semantics [24] as well as an efficient and robust implementation [19]. Oz has been used in many research projects [1, 5, 6, 7, 12, 11, 21, 29].

We take Oz as the foundation of our design because it provides four key concepts in a clear and formal way. First, Oz is a concurrent language, which is necessary since distributed systems are inherently parallel. Second, Oz has dataflow synchronization. Threads block when the data they require is not yet available. This blocking is invisible from the point of view of the thread. Third, Oz has first-class procedures with lexical scoping. This means that mobile procedures and objects will behave correctly no matter where they are executed. One might say that they take their environments with them. Fourth, Oz is state-aware: it makes a distinction between stateless and stateful data. Stateless data (which does not change) is replicated between sites. Stateful data (which can change) is the basis of an object system that models stationary servers and mobile agents as facets of the same concept (they are both objects).

1.3 Distributed Oz is almost Oz

To the programmer, a Distributed Oz program is almost identical to an Oz program. The latter is converted to the former with only minor modifications to the source text. For example, the graphic editor of Section 2 is made distributed by specifying the mobility behavior of the objects used to represent the picture state. In a first approximation, Distributed Oz extends Oz with just two notions specific to distribution: mobility control and asynchronous ordered communication. These concepts are defined in Section 4.2.

1.4 Organization of the paper

This paper is organized into five parts. Section 2 motivates the design by means of an example application written in Distributed Oz. Section 3 presents a set of high-level requirements that we assume the design must satisfy. The section then determines for each requirement what mechanisms are needed to achieve it. Section 4 defines the semantics of a language, Distributed Oz, whose language constructs provide these mechanisms. The centralized semantics of Distributed Oz are given in terms of a model called OPM (Oz

1The constraint programming part of Oz is outside the scope of this paper.

process

(Tcl/tk)

Graphics subsystem

User A

User C

User B

Distributed Oz

picture state

Objects for

Figure 1: A shared graphic editor

Programming Model). Section 5 gives examples to illustrate programming in Distributed Oz. Finally, Section 6 summarizes the graph model of distributed OPM execution, the mobility protocols for stateful entities (cells and ports), which are defined in terms of this model, and the model's implementation architecture.

2 A shared graphic editor

Writing an efficient distributed application can be much simplified by using transparency and mobility. We have substantiated this claim by designing and implementing a prototype shared graphic editor, an application which is useful in a collaborative work environment. The editor is seen by an arbitrary number of users. We wish the editor to behave like a shared virtual environment. This implies the following set of requirements. We require that all users can make updates to the drawing at any time, that each user sees his own updates without any noticeable delays, and that the updates must be visible to all users in real time. Furthermore, we require that the same graphical entity can be updated by multiple users. This is useful in a collaborative CAD environment when editing complex graphic designs. Finally, we require that all updates are sequentially consistent, i.e., each user has exactly the same view of the drawing at all times. The last two requirements are what makes the application interesting. Using multicast to update each user's visual representation, as is done for example in the wb whiteboard [14], does not satisfy the last two requirements.

Figure 1 outlines the architecture of our prototype. The drawing state is represented as a set of objects. These objects denote graphical entities such as geometric shapes and freehand drawing pads. When a user updates the drawing, either a new object is created or a message is sent to modify the state of an existing object. The object then posts the update to a distributed agenda. The agenda sends the update to all users so they can update their displays. The users see a shared stream, which guarantees sequential consistency.

New users can connect themselves to the editor at any time. The mechanism is extremely simple: the implementation provides primitives for saving and loading a language entity in a file named by a URL. We use URLs because of convenience. They are Ascii strings that are part of a