Published: 9th June 2010
DOI: 10.4204/EPTCS.27
ISSN: 2075-2180

EPTCS 27

Proceedings First International Workshop on
Decentralized Coordination of Distributed Processes
Amsterdam, The Netherlands, 10th June 2010

Edited by: Tom Van Cutsem and Mark Miller

Preface
Invited Presentation: Using the Web for decentralized coordination of distributed processes: you can get there from here
Tyler Close
1

Full Papers

On Secure Workflow Decentralisation on the Internet
Petteri Kaskenpalo
2
Separating Agent-Functioning and Inter-Agent Coordination by Activated Modules: The DECOMAS Architecture
Jan Sudeikat and Wolfgang Renz
17

Abstracts

A Wave-like Decentralized Reconfiguration Strategy for Self-organizing Resource-Flow Systems
Jan Sudeikat, Jan-Philipp Steghöfer, Hella Seebach, Wolfgang Reif, Wolfgang Renz, Thomas Preisler and Peter Salchow
32
A 90% RESTful Group Communication Service
Tadeusz Kobus and Paweł T. Wojciechowski
34

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:

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

Tyler Close (Google, USA)

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

Jan Sudeikat (Hamburg University of Applied Sciences)
Jan-Philipp Steghöfer (Augsburg University)
Hella Seebach (Augsburg University)
Wolfgang Reif (Augsburg University)
Wolfgang Renz (Hamburg University of Applied Sciences)
Thomas Preisler (Hamburg University of Applied Sciences)
Peter Salchow (Hamburg University of Applied Sciences)

Abstract

A domain in which self-organization is beneficial are production automation systems. In traditional production lines, resources are transported from one workstation to the other on conveyor belts or with similar, rigid and inflexible transportation mechanisms. While relatively easy to manage, these systems come to a complete halt whenever one of their constituent parts ceases to function. Also, if the requirements of the production lines change, the system will have to be retooled, a difficult, expensive, and time-consuming process. To add failure tolerance to such systems and to make this rigid structure more flexible, production automation systems could instead use autonomous guided vehicles (AGVs) that transport resources and robots that have several tools they can change in order to apply different capabilities as required [1]. We call this class of systems Self-Organizing Resource-Flow Systems with application domains in production automation and logistics. Their basic structure can be described with the Organic Design Pattern (ODP) [2]. Resources are processed according to a task by independent agents. Each agent has a number of capabilities it can apply to the resource to alter it according to the task. Agents can exchange resources with other agents as, e.g., given by the layout of a shop floor.

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 SodekoVS1 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

[1]  A. Hoffmann, F. Nafz, H. Seebach, A. Schierl & W. Reif (2010): Developing Self-organizing Robotic Cells using Organic Computing Principles. In: Workshop on Bio-Inspired Self-Organizing Robotic Systems, Proceedings of the International Conference on Robotics and Automation 2010.
[2] H. Seebach, F. Ortmeier & W. Reif (2007): Design and Construction of Organic Computing Systems. IEEE Congress on Evolutionary Computation, 2007, pp. 4215-4221.
[3] J. Sudeikat, L. Braubach, A. Pokahr, W. Renz & W. Lamersdorf (2009): Systematically Engineering Self-Organizing Systems: The SodekoVS Approach. Electronic Communications of the EASST 17. ISSN 1863-2122.
[4] J. Sudeikat & W. Renz (2009): Programming Adaptivity by Complementing Agent Function with Agent Coordination: A Systemic Programming Model and Development Methodology Integration. Communications of SIWN 7, pp. 91-102. ISSN 1757-4439.

Footnote:

1Acknowledgments: This research is partly sponsored by the German research foundation (DFG) in the project SodekoVS and in the DFG special priority program "Organic Computing" (SPP 1183) in the project SAVE ORCA.

A 90% RESTful Group Communication Service

Tadeusz Kobus (Poznań University of Technology)
Paweł T. Wojciechowski (Poznań University of Technology)

Abstract

In this paper we introduce a 90% RESTful group communication service that we have developed for resilient Web applications. Our system is based on Spread—a popular group communication toolkit which delivers many useful programming abstractions, such as various reliable ordered broadcasts; they can be used, e.g. for implementing systems tolerant to server crashes. Contrary to Spread and many other such systems available as libraries of programming languages, we represent group communication abstractions as resources on the Web, addressed by URIs. To our best knowledge, this is the first approach to engineering group communication systems in this way.

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

[1]  Roy T. Fielding & Richard N. Taylor (2002): Principled design of the modern Web architecture. ACM Transactions on Internet Technology (TOIT) 2(2), pp. 115-150.
[2] Rohit Khare & Richard N. Taylor (2004): Extending the Representational State Transfer (REST) Architectural Style for Decentralized Systems. In: Proceedings of ICSE '04, pp. 428-437.
[3] Tadeusz Kobus & Pawe  T. Wojciechowski (2010): A 90% RESTful Group Communication Service. Technical Report RA-02/10, Institute of Computing Science, Pozna\'n University of Technology.
[4] RESTGroups (2010). http://www.cs.put.poznan.pl/pawelw/restgroups/.
[5] Fred B. Schneider (1993): Replication management using the state-machine approach. In: Sape Mullender, editor: Distributed Systems (2nd Ed.), ACM Press/Atdison-Wesley Publishing Co., pp. 169-197.
[6] Spread Concepts LLC (2006). The Spread Toolkit. http://www.spread.org/.

Acknowledgements:

This work has been partially supported by the Polish Ministry of Science and Higher Education within the European Regional Development Fund, Grant No. POIG.01.03.01-00-008/08.