APICe » Publications » On the Expressiveness of Linda Coordination Primitives

On the Expressiveness of Linda Coordination Primitives

Nadia Busi, Roberto Gorrieri, Gianluigi Zavattaro
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.
Information and Computation 156(1-2), pages 90-121, January 2000.
Catuscia Palamidessi, Joachim Parrow, Rob van Glabbeek (eds.), Elsevier Science Publishers B. V., Amsterdam, The Netherlands
@article{lindacoord-inco156,
	Address = {Amsterdam, The Netherlands},
	Author = {Busi, Nadia and Gorrieri, Roberto and Zavattaro, Gianluigi},
	Doi = {10.1006/inco.1999.2823},
	Editor = {Palamidessi, Catuscia and Parrow, Joachim and van Glabbeek, Rob},
	Issn = {0890-5401},
	Journal = {Information and Computation},
	Month = {10~} # jan,
	Number = {1-2},
	Pages = {90--121},
	Publisher = {Elsevier Science Publishers B. V.},
	Title = {On the Expressiveness of {L}inda Coordination Primitives},
	Volume = 156,
	Year = 2000}