Preface

This volume contains the papers presented at the first International Workshop on Decentralized Coordination of Distributed Processes, DCDP 2010, held in Amsterdam, The Netherlands on June 10th, 2010 in conjunction with the 5th International Federated Conferences on Distributed Computing Techniques, DisCoTec 2010.

The central theme of the workshop is the decentralized coordination of distributed processes. Decentralized meaning there is no single authority in the network that everything is vulnerable to. Coordinated meaning processes need to cooperate to achieve meaningful results, potentially in the face of mutual suspicion. Distributed, meaning processes are separated by a potentially unreliable network.

The workshop opened with a Keynote by Tyler Close (Google) titled "Using the Web for decentralized coordination of distributed processes. You can get there from here." Afterwards authors presented two full papers and two extended abstracts.

We wish to thank all members of the Program Committee who carefully reviewed the submissions:

• Fred Spiessens, Evoluware, Belgium
• Carl Hewitt, MIT EECS (Emeritus), USA
• Ben Laurie, Google, UK
• Alan Karp, Hewlett-Packard, USA
• Peter Van Roy, Universite Catholique de Louvain, Belgium
• Dean Tribble, Microsoft, USA
• Toby Murray, University of Oxford, UK
• Tyler Close, Google, USA
• Mark Miller, Google, USA
• Tom Van Cutsem, Vrije Universiteit Brussel, Belgium

We also thank Tyler Close for willing to give a Keynote speech. We thank Marcello Bonsangue for giving us the chance to organize this workshop at DisCoTec, and to the Editorial Board of the Electronic Proceedings in Theoretical Computer Science (EPTCS) for publishing the workshop proceedings.

Tom Van Cutsem and Mark S. Miller
DCDP 2010 Organizers

Using the Web for decentralized coordination of distributed processes: you can get there from here

At first blush, the Web might not seem like a good starting place for decentralized coordination of distributed processes. A typical Web application is vulnerable to multiple central authorities and so is not decentralized. Most often, coping with the travails of distribution depends upon human intervention via the browser's 'refresh' button; which doesn't bode well for headless processes. Coordination between Web applications, where it's done at all, often results in complete vulnerability between participants. Looking at the Web as a platform for decentralized coordination of distributed processes, it seems reasonable to conclude: "You can't get there from here".

Sometimes, a different perspective is all that is needed to find a way forward out of the maze. In this talk, we'll reacquaint ourselves with the Web's core technologies: the URL, HTTP and TLS. With a fresh outlook on these technologies, we'll explore how to use them for the desired effect, while still working within the existing Web infrastructure. Using simple and compatible extensions to the Web, we'll study cases where we can now coordinate the formerly intractable. The Waterken Server and an extended Web browser enable demonstration of these implementation techniques. With a different perspective on where "here" is, we'll get "there".

Abstract of keynote speech given at DCDP 2010 by Tyler Close (Google, USA)

A Wave-like Decentralized Reconfiguration Strategy for Self-organizing Resource-Flow Systems

Abstract

In this paper, we propose a decentralized, self-organizing process for the class of self-organizing resource-flow systems. This process is analyzed and modeled with the tools provided by the SodekoVS¹ project [3]. Agents change their local configurations until the system in its entirety has restored a stable state. During reconfiguration, parts of the system that are not affected by the process or have already been reconfigured are still able to resume their normal work.

The utilization of self-organization principles in the development of distributed software systems is considered in the research project "Selbstorganisation durch Dezentrale Koordination in Verteilten Systemen" (SodekoVS) [3]. The supplementation of self-organizing features to software systems is based on the externalization of coordination models [4]. A coordination middleware serves as a reference model for the integration of decentralized self-organizing processes in MAS. It contains two types of functional elements for the encapsulation of these aspects. First, agents are connected with each other via so-called Coordination Media. These are communication infrastructures that allow to encapsulate specific interaction modes. Secondly, the utilization of these media is separated from the agent-logic by associating agents with Coordination Endpoints. They initiate and participate in medium-mediated interactions on behalf of the associated agents and effectuate modifications on agents when appropriate. This middleware separates and automates the activities, i.e. interactions and local adjustments, that are conceptually related to coordination.

This reference architecture has been used to realize a completely decentralized reconfiguration approach. It is based on the idea that a wave of role re-allocation runs through the system in order to re-establish the resource-flow. Assuming that each agent is capable to exhibit a set of capabilities, a correct resource flow can be (re-)established by the appropriate swapping of roles. Failing agents adopt actable roles and in return other agents help out by providing the unactable roles. Waves of reallocations originate from the failing agents as these send requests for assistance along the resource flow. Recipients of these request decide locally whether they are capable and willing to swap roles. Depending on the system configuration, it may be the case that a single swap of roles does not reestablish the correct sequence of activities, thus transitive changes of roles are required. Prior to the detailed design and embedding of this decentralized process, we anticipated the resulting system dynamics. The decentralized reconfiguration is transfered to a stochastic π-calculus model that can be simulated. Then the decentralized reconfiguration strategy has been realized on top of an agent-based simulation model of production lines. This implementation makes use of the freely available Jadex agent framework [3]. A realization of the Coordination Middleware for this agent platform is utilized [4]. Evaluations show the quick convergence to stable states and the reconfigurations only affect system partitions.

The outlined algorithm works by exchanging responsibilities with neighboring agents and by propagating change requests until all of them could be satisfied. Thus, the reconfiguration propagates through the system like a wave. An interesting aspect of the proposed mechanism is that configuration changes are preferred to happen in the neighborhood of the deficient agents. By keeping the reconfiguration local, other parts of the system are not impaired by a failure and can continue to run normally. Future work includes a more detailed elaboration of the combination of top-down design methodologies as promoted with the ODP and bottom-up design of coordination methods as proposed in SodekoVS. This will also include a comparison of their respective advantages and problems.

References

Footnote:

A 90% RESTful Group Communication Service

Abstract

The Web can provide a common, language-independent platform for interoperable resilient services that work together to create seamless and robust systems. Service resilience, defined as the continued availability of a service despite failures and other negative changes in its environment, is vital in the Service-Oriented Architecture (SOA). We must ensure that each service is highly available regardless of unpredictable conditions, such as sudden and significant degradation of network latency or failure of dependant services. In this paper, we sketch our work on group communication service which can be used for implementing resilient Web services, based on REST [1]; see the technical report [3] for a full description.

A typical way of increasing service resilience is to replicate it. Service replication means deployment of a service on several server machines, each of which may fail independently, and coordination of client interactions with service replicas. A general model of such replication is called replicated state machine [5]. The key abstractions required to implement this model are provided by group communication systems. They provide various primitives for: a) detection of malfunctioning/crashed processes, b) reliable point-to-point transfer of messages, c) formation of processes into groups, the structure of which can change at runtime, and d) reliable message multicasting with a wide range of guarantees concerning delivery of messages to group members (e.g.. causally- , fifo- and totally-ordered message delivery). Notably, the overlay protocols for reliable multicasting do not depend on any central server, so that there is no single point of failure. For this, distributed agreement protocols must be used.

For the past 20+ years, many group communication systems have been implemented (see [3] for references). Unfortunately, various group communication systems usually have quite different application programming interfaces, which are non-standard, complex and language/platform dependent. Moreover, many of such systems are monolithic, i.e.. it is not possible to replace their protocols or add new features. Using these systems to implement SOA services makes the code of services not easily reusable nor manageable (adaptable), which is a counterexample to the Service-Oriented Architecture.

We propose an approach to designing an API of a group communication system, which is based on the REpresentational State Transfer (REST) [1]. Typically REST uses HTTP and its methods GET, PUT, POST, and DELETE. This makes it easy to describe one RESTful Web service call to another Web service, e.g.. a replicated service call to a group communication service. We need only supply a verb, a URI and (optionally) a few headers containing the message payload. Thus, REST gives us a uniform, simple way of using group communication abstractions by Web applications, fulfilling the SOA requirements, such as language/platform independence and easy software integration. Moreover, the use of HTTP usually enables us to communicate with servers behind fire-walls.

However, we had to solve some problems to realize this approach, mostly related to the REST characteristics and the constraints imposed on HTTP. For example, the client would not be able to change state based on the responses of intermediary service calls; also, we had to provide means for the client to communicate both synchronously and asynchronously with the group communication service using purely the HTTP methods; and we needed to match error codes of the HTTP protocol to the incorrect behaviour of a group communication system.

Various authors pointed out significant limitations of the REST architecture style. For example, Khare and Taylor [2] discussed some of the limitations and proposed several extensions of REST (collectively called ARRESTED). They allow to model the properties required by distributed and decentralized systems. Similarly to them, we are not bound by the rules of the original model. REST cannot model group communication well. Therefore our goal was rather to design the RESTful interface to group communication, albeit sacrificing strict conformance to the original REST model. To emphasize that group communication cannot fully conform to REST, we say that our approach is "90% RESTful".

To illustrate our ideas, we have been developing RESTGroups-a group communication programming tool that can be used for developing resilient services on the Web. RESTGroups is an extension of Spread [6] with a daemon and an API based on (some % of) REST over the standard HTTP. We think that the benefits of using our tool overcome the lack of REST purity. RESTGroups functions as a front-end for Spread that is architecture- and language-independent, i.e.. communicating services can be implemented with the use of a variety of programming languages and can run on different platforms.

RESTGroups provides a representation of Spread group communication services as resources, identified by URIs, with a simple but powerful API that only uses the following methods of the HTTP protocol for invoking the services: GET is used to retrieve data (for example, a message) or perform a query on a resource; the data returned from the RESTGroups service is a representation of the requested resource; POST is used to create a new resource (for example, to extend a process group with a new process or to send/broadcast a new message); the RESTGroups service may respond with data or a status indicating success or failure; PUT is used to update existing resources or data; and DELETE is used to remove a resource or data (for example, to remove a process from a process group). In some cases, the update and delete actions may be performed with POST operations as well. To our best knowledge, it is the first attempt to a RESTful group communication service; the distribution files and javadoc are available [4].

References

Acknowledgements: