Towards a Hierarchy of Negative Test Operators for Generative Communication

   page       BibTeX_logo.png   
Gianluigi Zavattaro
EXPRESS '98, Fifth International Workshop on Expressiveness in Concurrency (Satellite Workshop of CONCUR '98), pages 154-170
Electronic Notes in Theoretical Computer Science 16(2)
Elsevier Science B.V.

Generative communication is a coordination paradigm that permits interprocess communication via the introduction and consumption of data to and from a shared common data space. We call negative test operators those coordination primitives able to test the absence of data in the common data space. In this paper we investigate the expressive power of this family of operators. To this aim, we concentrate on three possible primitives differing in the ability of instantaneously producing new data after the test: tfa(a) tests the absence of data of kind a, t&e(a) instantaneously produces a new occurrence of datum a after having tested that no other occurrences are available, t&p(a,b) atomically tests the absence of data a and produces one instance of datum b. We prove the existence of a strict hierarchy of expressiveness among these operators.