Expressive Power of the ACLT Reaction Specification Language


Enrico Denti, Antonio Natali, Andrea Omicini

Department of Electronics, Computer Science and Systems (DEIS), Università di Bologna
LIA Series 26(DEIS-LIA-97-009)
1997

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.

(keywords) Multi-agent systems, Coordination, Tuple Spaces, Petri Nets, Programmable Coordination Media, Turing Equivalence

Publication

— authors

— status

published

— sort

technical report

— publication date

1997

— series

LIA Series

— volume

26

— issue

DEIS-LIA-97-009

— venue

DEIS LIA TR

— address

Bologna, Italy

— institution

Department of Electronics, Computer Science and Systems (DEIS), Università di Bologna

files

Open Access PDF

Partita IVA: 01131710376 — Copyright © 2008–2023 APICe@DISI – PRIVACY