X-Sun-Data-Type: default X-Sun-Data-Name: andreoli.html X-Sun-Charset: us-ascii X-Sun-Content-Lines: 269 Flexible Coordination of Distributed Active Objects

Flexible Coordination of Distributed Active Objects

Jean-Marc Andreoli and Remo Pareschi

The Object paradigm seems quite natural for developing distributed applications: ideally, a complex application is obtained by simply assembling re-usable objects and having them interact through standard mechanisms (mainly, synchronous method invocation for passive objects or asynchronous message passing for active objects). However, the patterns of interaction between distributed objects in an application are often quite complex, and also call for re-usability. Of course, patterns of interaction could be captured inside specialized objects, working as ``software conductors'', being themselves connected to other objects through the basic mechanisms of method invocation or message passing, and coordinating them. But programming such objects is not an easy task, because of the gap between the fine-grain, low-level control mechanisms offered by most traditional programming languages and the coarse-grain, high-level coordination mechanisms needed to capture interaction patterns between autonomous objects. This leads to several lines of research:

Distributed object coordination [13, 6];
Actors synchronization and filtering [1, 4];
Script based programming [3] as in AppleScript (Apple Inc.), Tcl (Sun), VisualBasic (Microsoft)...;
Coordination of software components through shared message services a la Linda [5] (e.g. message buses, message queues), as in ToolTalk (Sun), MQ series (IBM)...;

All these cases assume an ubiquitous coordination service, available at all the sites of a distributed applications. In the last two cases, the coordination service is accessed explicitly, directly from traditional programming languages, through appropriate libraries made available to application programmers. On the contrary, in the first two cases, the basic objects of the application are (supposedly) unaware of the coordination, which is implict, but can be programmed using specialized languages.

In this position paper, we investigate another approach to the problem of coordination in distributed systems: instead of keeping the traditional object model and building a coordination layer as a side service to it, we propose to enrich the object model with general purpose primitives which can then be exploited for coordination. The difficulty is to find the appropriate set of primitives so as to be as general purpose as possible.

A possible source of inspiration for this purpose is the abundant work in the domain of multi-agent systems, in particular around the notion of ``speech acts'' [12]. From an abstract point of view, the foundation of the traditional object model relies on two speech acts:

Perform Service at Object
for synchronous method invocation in a client server architecture;
Notify Event at Object
for asynchronous message passing in a peer-to-peer architecture.

Furthermore, in most systems where these two kinds of speech acts are allowed, they are, structurally, totally unrelated: they are only related by the way they are arranged in the applications. Distributed Artificial Intelligence is rich in much more refined sets of speech acts, generally oriented towards specific domains of applications, such as cooperative problem solving (e.g. Contract nets [9]).

In the CLF project (Coordination Language Facility) at the Rank Xerox Research Centre, we first proposed an enriched object model, in particular in terms of the set of speech acts it supports, and then investigated the benefits of this extension for coordination [2]. Of course, we wished to keep the universal flavor of objects, and not be biased towards any specific application framework. A concise way of explaining our proposed object model is to use an anthropomorphic metaphor, a usual practice when talking of autonomous active objects. Consider for example the activity of a human agent interacting with a browser for the World Wide Web (the archetypical client server architecture) to retrieve some information or some service. This in itself is sometimes a complex process, from which we can distinguish three main phases: a Preparation phase to determine the URL of the resource capable of providing the requested information (e.g. using Web search engines); a Performance phase in which the URL is actually accessed and further interaction with the resource may occur (e.g. through forms); a Notification phase, although this is less obvious in the case of current practice on the Web, where the client may suggest an extension of a service (e.g. sending a mail to a Web site saying ``I want my paper to appear in your bibliography service'').

The CLF object model proposes general purpose primitive speech acts at the object level, capable of supporting the three above mentionned phase of the interaction with a service. These primitives assume that, in an interaction, the server is viewed as resource manager offering basically two kinds of services -- insertion and removal of resources -- and the client is viewed as a resource manipulator trying to invoke these services. No assumption is made on the nature of the resources: they may even be virtual, and are only manipulated associatively through their properties.

Preparation phase

: Inquire Property at Object
In this phase, the client sends a property to the server and expects, in return, a stream of replies, each reply consisting of

the identifier of an action capable of removing a resource having the given property;
possibly, some more information about the properties of the resource which can be removed by that action.

At this point, none of the actions returned are effectively executed. Notice that, a priori, an Inquiry lasts forever: any change of state of the server may generate new replies.

Performance phase

: Reserve/Confirm/Cancel Action
The client may then wish to execute some of the actions returned by an Inquiry. However, at the time execution is requested, the server may have changed its state and the action may not be available anymore. To deal with this possibility of failure, we propose here to incorporate in the model, directly at the object level, some rudimentary transaction facilities, basically the means to realize a two-phase commit protocol. The Reserve operation requires the server to reserve all the resources needed by an action (passed in argument). A reservation returns either success or failure, if the action has been invalidated by a change of state in the server. The Confirm/Cancel operations either commit or abort the execution of an action which has been successfully reserved (hence cannot fail). No results are expected.

Notification phase

: Insert Property at Object
In this phase, the client requests that some resource satisfying a given property be inserted in the server.

These primitives combine in a single framework both asynchronous, synchronous and defered synchronous communication modes. Furthermore, it implies some structural constraints on the invocations of the different operations (a Reservation must always be invoked on the result of an Inquiry; it is an error to Confirm/Cancel an action which has not been successfully Reserved). Notice that encapsulation is strictly respected: the server is completely free to implement the operations of the protocol in its own way. The server must only publish a set of interfaces for the clients to use. Notice also that in the defered synchronous operation (Inquiry), the returned stream of answers may be infinite: in this case, the server becomes an event generator for events subscribed by the client in the argument of the Inquiry.

Apart from the object model just described, we have also defined a scripting language for this model (in fact, it is this language which is called the CLF). It is based on rules, each rule defining in a very concise way a complex combination of all the basic operations of the protocol. Using this language has suggested a number of planned or already realized extensions of the protocol, in particular:

Operations have been added to allow clients to kill an Inquiry (i.e. ``unsuscribe'' to the corresponding events), or to check whether an answer to an Inquiry is still valid (i.e. perform a ``light-weight'' reservation).
More sophisticated transaction primitives than two-phase commit could be incorporated, especially for the treatment of long-lived transactions, a topic widely investigated by the transaction community [8, 11, 10].
The Inquiry operation realizes some rudimentary form of negotiation between a client and a server in order to determine an action to take. The negotiation mechanism is still limited by the defered synchronous nature of the Inquiries, but more refined negotiation protocols could be incorporated. A good source of inspiration, from that point of view, is the abundant litterature on constraint propagation (see [7] for an overview): constraint propagation is the archetypical ``general purpose'' negotiation mechanism.

References

1: M. Aksit, K. Wakita, J. Bosch, and L. Bergmans. Abstracting object interactions using composition filters. In R. Gerraoui, O. Nierstrasz, and M. Riveille, editors, Object Based Distributed Processing. Springer Verlag, Berlin, Germany, 1994.
2: J-M. Andreoli, S. Freeman, and R. Pareschi. The coordination language facility: Coordination of distributed objects. Theory and Practice of Object Systems, 1996. To appear.
3: W. Cook and W. Harris. The open scripting architecture: Automating, integrating, and customizing applications, 1993. Available here.
4: S. Frølund and G. Agha. A language framework for multi-object coordination. In Proc. of ECOOP'93, Kaiserslautern, Germany, 1993.
5: D. Gelernter. Generative communication in Linda. ACM Transactions on Programming Languages and Systems, 7(1):80-112, 1985.
6: R. Helm, I. Holland, and D. Gangopadhyay. Contracts: Specifying behavioral compositions in object oriented systems. In Proc. of OOPSLA/ECOOP'90, Ottawa, Ont., Canada, 1990.
7: V. Kumar. Algorithms for constraint-satisfaction problems. AI Magazine, Spring:32-44, 1992.
8: M. Rusinkiewicz and A. Sheth. Specification and execution of transactional workflows. In W. Kim, editor, Modern Database Systems. Addison-Wesley, Reading, Ma, U.S.A., 1995.
9: R.G. Smith. The contract net protocol: High level communication and control in a distributed problem solver. IEEE Trans. Comput., 29(12):1104-1113, 1980.
10: H. Wächter and A. Reuter. The contract model. In A. Elmagarmid, editor, Database Transaction Models for Advanced Applications. Morgan Kaufmann Publishers, San Mateo, Ca, U.S.A., 1993.
11: G. Weikum and H-J. Scheck. Concepts and applications of multilevel transactions and open nested transactions. In A. Elmagarmid, editor, Database Transaction Models for Advanced Applications. Morgan Kaufmann Publishers, San Mateo, Ca, U.S.A., 1993.
12: T. Winograd. A language/action perspective on the design of cooperative work. Human Computer Interaction, 3(1):3-30, 1988.
13: D. Yellin and E. Strom. Interfaces, protocols and the semi-automatic construction of software adaptors. In Proc. of OOPSLA'94, Portland, Or, U.S.A., 1994.