Distributed Coordination

The motivation: How to compose and coordinate distributed hosts?

Large distributed computational units can be built by the composition of simpler atomic units. Coordination of web services are a good example of such systems.

The coordination of distributed services or components is sometimes performed by multiple hosts, each imposing its own constraints, whereas a global consensus must be achieved.

The coordination language Reo addresses this problem providing high level abstractions for coordination. The Distributed Reo project aims to develop a distributed implementation of Reo, making it easy to develop and deploy complex coordinating systems.

The Architecture

Which steps are involved from design until execution?

ReDrum is based on the following layered model. Designers develop Reo connectors using our GUI environment and provide partial deployment information. The engine fully resolves the deployment, optimizes connectors (locally to each physical machine), and instantiates appropriate implementations to run on a distributed kernel.

  • Designer - Developers use our Eclipse Coordination Tools to design Reo connectors and specify some deployment constraints, i.e., where some primitive's ports are to be executed. The developer can provide some constraints and policies to guide the deployment process.
  • Deployment Resolver - Unknown locations of where the connector will be executed are resolved, following the deployment policy.
  • Local optimizer - Each local chunk of a connector is optimized, based on what information is known about its behaviour. An equivalent, more efficient, implementation can be generated. The architecture will support plug-ins to easily introduce new local optimizations.
  • Instantiator - Generates the actual code to execute primitives. The code is originated either from originally specified primitives or as a result of local optimization.
  • Kernel - Executes the connector across the network.
From design to distributed executable code.

Implementation

What kind of code is being used?

Detailed description of the implementation, with source code, can now be found in the Reo development section.

Based on Scala's Actor Model, running on JVM (Java).

The kernel operates on primitives connected via nodes. Both primitives and nodes can be distributed. Each primitive has only partial information about the connector: primitives only know their neighbours.

  • Coordination Primitive
    • Has several (distributed) ports that can be connected to nodes;
    • Messages flowing on ports obey a certain protocol to ensure correct (synchronous) behaviour of the whole connector.

  • Node
    • Stateless connector that propagates synchronous constraints;
    • Glues different locations.
Connection between primitives over a network.

Distributed Agreement

How to agree in an atomic step?

A 2-phase algorithm resolves synchronization constraints:

  • Negotiation - all involved parties commit to a possible behaviour.
  • Communication - behaviour and data propagate across the connector.

The algorithm is distributed and concurrent, and multiple parties can initiate the interaction. The algorithm requires ordering on parties RED > ORANGE > GREEN, which means red requests overrule other requests.

Initial State Requests Commit
End of commit Dataflow

More tools and formalisms

What does the theory brings?

The underlying behaviour of a distributed connector is based on the Connector Colouring semantics for Reo. The Eclipse Coordination Tools incorporate a model checker and automatic generation of animations for Reo connectors, among other facilities, which allow verification and visualization of the behaviour of the resulting systems. We plan to extend this framework to generate and deploy code automatically. The architecture can integrate different coordination models for a unified approach to distributed application development.

About

This work is being developed at CWI, by José Proença, Dave Clarke and Farhad Arbab. The ideas behind this project were already presented in several workshops and meeting. You can find the slides below, from the most recent to the older. ( SYANCO'08, CoCoCo'08 , CIC'07 , ACG meeting) We count with the support of the Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO), the Fundação para a Ciência e a Tecnologia (FCT---grant 22485-2005), the project Developing a Compositional Calculus of Component Connectors (C-Quattro), and the Centrum voor Wiskunde en Informatica (CWI).