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},
}