Comparing communication primitives via their relative expressive power

In this paper, we study 16 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 have already been used in at least one language which has appeared in the literature; however, to reason uniformly on such primitives, we plug them into a common framework based on the pi. 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. (C) 2008 Elsevier Inc. All rights reserved.