Expressive Power of the ACLT Reaction Specification Language

The notion of programmable coordination medium as a shared communication device whose behaviour can be defined according to the global system needs has indeed an impact over the design of multi-component software systems. In fact, it allows coordination systems to be organised around a high-level inter-component interaction protocol, while the low-level details are delegated to properly programmed communication abstractions. this leads to a shift of (part of) the computational charge of a multi-component system from the communicating components (agents) to the communication device, and raises the issue of the expressive power of a programmable coordination medium.

As an example, this paper discusses the case of ReSpecT, the first-order language used by the ACLT coordination model to specify and define the behaviour of its multiple programmable tuple spaces. Its expressiveness is compared with that of Petri Nets (and of some of the variants and extensions), taken as a reference as one of the most used formalisms for the specification and design of concurrent and distributed systems. In particular, we show that ReSpecT is Turing-powerful. This makes it possible for the designer of a multi-component architecture to freely split the system's computational load between the communicating components and the communication device, so that local and global properties of a coordination system can be respectively embodied into the coordination entities (ACLT agents) and the coordination media (ACLT programmable logic tuple spaces) in the most natural way.