The Paper appeared in Information and Computation; it extends and improves two preliminary works published at FoSSaCS'06 and EXPRESS'06.
In this paper, we study sixteen communication primitives, arising from the combination of four useful programming features: synchronism (synchronous vs asynchronous primitives), arity (monadic vs polyadic data), communication medium (message passing vs shared dataspaces) and pattern-matching. Some of these primitives has already been used in at least one language appeared in literature; however, to uniformly reason on such primitives, we plug them in a common framework based on the pi-calculus. By means of possibility/impossibility of `reasonable' encodings, we compare every pair of primitives to obtain a hierarchy of languages based on their relative expressive power.
@article{G:IC08, author = {D. Gorla}, title = {Comparing Communication Primitives via their Relative Expressive Power}, journal = {Information and Computation}, volume = {206}, number = {8}, pages = {931--952}, year = {2008}, publisher = {Elsevier}, }