On the Expressive Power of a Language for Programming Coordination Media

A programmable coordination medium is a shared communication device whose behaviour can be defined by means of a suitable programming language according to the global system needs. This notion has indeed an impact over the design of multi-component software system, since (part of) the system computational charge of can be in principle shifted from the communicating components (agents) to the communication device.

At the same time, this raises the issue of the computational power of a programmable coordination medium, and of its expressiveness. As a meaningful example, this paper discusses the case of ReSpecT, the first-order logic language used by the ACLT coordination model to define the behaviour of its multiple programmable logic tuple spaces, called tuple centres. Its expressiveness is discussed first by comparing ReSpecT with Petri Nets, taken as a reference model for the specification and design of concurrent and distributed systems, then by presenting some simple cases of coordination systems designed around ReSpecT-programmed logic tuple spaces. Finally, we show that ReSpecT is Turing-powerful. This makes it possible to freely split the computational load of an ACLT-based architecture between the communicating components and the communication device according to the design needs. In particular, this allows local and global system properties to be embodied where they naturally fit in, that is, respectively, into the coordination entities (ACLT agents) and the coordination media (ACLT tuple centres).