On the Expressiveness of Linda Coordination Primitives

Nadia Busi, Roberto Gorrieri, Gianluigi Zavattaro

Information and Computation 156(1-2), pages 90-121
January 2000

We introduce a process algebra containing the coordination primitives of Linda (asynchronous communication via a shared data space, read operation, nonblocking test operators on the shared space). We compare two possible semantics for the output operation: the former, that we call ordered, defines the output as an operation that returns when the message has reached the shared data space; the latter, that we call unordered, returns just after sending the message to the tuple space. The process algebra under the ordered semantics is Turing powerful, as we are able to program any random access machine. The main result of the paper is that the process algebra under the unordered semantics is not Turing powerful. This result is achieved by resorting to a net semantics in terms of contextual nets (P/T nets with inhibitor and read arcs) and by showing that there exists a deadlock-preserving simulation of such nets by finite P/T nets, a formalism where termination is decidable.



— authors

Nadia Busi, Roberto Gorrieri, Gianluigi Zavattaro

— editors

Catuscia Palamidessi, Joachim Parrow, Rob van Glabbeek

— status


— sort

article in journal

— publication date

January 2000

— journal

Information and Computation

— volume


— issue


— pages


— address

Amsterdam, The Netherlands


original PDF




— print ISSN


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