Comparing Communication Primitives via their Relative Expressive Power

Daniele Gorla

The Paper appeared in Information and Computation; it extends and improves two preliminary works published at FoSSaCS'06 and EXPRESS'06.


Abstract:

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

Home page / Publications