Comparing three semantics for Linda-like languages

AbstractA simple calculus based on generative communication is introduced; among its primitives, it contains a conditional input operation that tests for presence (or absence) of an output, reminiscent of the inp predicate of Linda. We study three different semantics for the output operation, called instantaneous, ordered and unordered, and we compare these approaches from two different points of view. First, we investigate the associated behavioural semantics by characterizing the coarsest congruence contained in the barbed bisimulation. We obtain the following results: in the instantaneous case the coarsest congruence is a variant of asynchronous bisimulation while, for the ordered and unordered semantics, we obtain a small variant of the classic (synchronous) bisimulation. Moreover, the three obtained congruences are pairwise different. Then, we compare the expressiveness of the three approaches. We first list a class of coordination primitives that are directly implementable in our calculus under the instantaneous semantics but not under the ordered one. Finally, we show that the calculus is Turing powerful under the instantaneous and ordered approaches, whereas this is not the case for the unordered semantics. Thus, we conclude that there exists a strict expressiveness hierarchy among the three semantics