# zbMATH — the first resource for mathematics

Comparing communication primitives via their relative expressive power. (English) Zbl 1169.68009
Summary: 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 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.

##### MSC:
 68N15 Theory of programming languages 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
##### Software:
PiDuce; Pict; Linda; XPi
Full Text:
##### References:
 [1] L. Acciai, M. Boreale, Xpi: a typed process calculus for XML messaging, in: Proceedings of FMOODS’05, vol. 3535 of LNCS, Springer, 2005, pp. 47-66. · Zbl 1146.68050 [2] Amadio, R.M.; Castellani, I.; Sangiorgi, D., On bisimulations for the asynchronous $$\pi$$-calculus, Theoretical computer science, 195, 2, 291-324, (1998) · Zbl 0915.68009 [3] Arnold, K.; Freeman, E.; Hupfer, S., Javaspaces principles, patterns and practice, (1999), Addison-Wesley [4] Arun-Kumar, S.; Hennessy, M., An efficiency preorder for processes, Acta informatica, 29, 8, 737-760, (1992) · Zbl 0790.68039 [5] G. Boudol, Asynchrony and the $$\pi$$-calculus (note), Rapport de Recherche 1702, INRIA Sophia-Antipolis, May 1992. [6] A. Brown, C. Laneve, G. Meredith, $$\pi$$duce: a process calculus with native XML datatypes, in: Proceedings of 2nd International Workshop on Services and Formal Methods, vol. 3670 of LNCS, Springer, 2005, pp. 18-34. [7] Busi, N.; Gorrieri, R.; Zavattaro, G., A process algebraic view of linda coordination primitives, Theoretical computer science, 192, 2, 167-199, (1998) · Zbl 0895.68016 [8] Busi, N.; Gorrieri, R.; Zavattaro, G., Comparing three semantics for linda-like languages, Theoretical computer science, 240, 1, 49-90, (2000) · Zbl 0954.68092 [9] Busi, N.; Gorrieri, R.; Zavattaro, G., On the expressiveness of linda coordination primitives, Information and computation, 156, 1-2, 90-121, (2000) · Zbl 1046.68616 [10] Busi, N.; Zavattaro, G., On the expressive power of movement and restriction in pure mobile ambients, Theoretical computer science, 322, 3, 477-515, (2004) · Zbl 1071.68072 [11] D. Cacciagrano, F. Corradini, On synchronous and asynchronous communication paradigms, in: Proceedings of ICTCS’01, vol. 2202 of LNCS, Springer, 2001, pp. 256-268. · Zbl 1042.68614 [12] D. Cacciagrano, F. Corradini, C. Palamidessi, Separation of synchronous and asynchronous communication via testing, in: Proceedings of EXPRESS’05, ENTCS, vol. 154, no. 3, 2006, Elsevier, pp. 95-108. · Zbl 1273.68251 [13] Carbone, M.; Maffeis, S., On the expressive power of polyadic synchronisation in $$\pi$$-calculus, Nordic journal of computing, 10, 2, 70-98, (2003) · Zbl 1062.68077 [14] Cardelli, L.; Gordon, A., Mobile ambients, Theoretical computer science, 240, 1, 177-213, (2000) · Zbl 0954.68108 [15] G. Castagna, R. De Nicola, D. Varacca, Semantic subtyping for the $$\pi$$-calculus, in: Proceedings of LICS, IEEE Computer Society, 2005, pp. 92-101. · Zbl 1146.68052 [16] de Boer, F.; Palamidessi, C., Embedding as a tool for language comparison, Information and computation, 108, 1, 128-157, (1994) · Zbl 0788.68014 [17] De Nicola, R.; Gorla, D.; Pugliese, R., On the expressive power of klaim-based calculi, Theoretical computer science, 356, 3, 387-421, (2006) · Zbl 1092.68070 [18] R. De Nicola, D. Gorla, R. Pugliese, Pattern matching over a dynamic network of tuple spaces, in: Proceedings of FMOODS’05, vol. 3535 of LNCS, Springer, 2005, pp. 1-14. [19] C. Ene, T. Muntean, Expressiveness of point-to-point versus broadcast communications, in: Proceedings of 12th Symposium on Fundamentals of Computation Theory, vol. 1684 of LNCS, Springer, 1999, pp. 258-268. · Zbl 0946.68096 [20] D. Ford, T. Lehman, S. McLaughry, P. Wyckoff, T Spaces, IBM Systems Journal (1998) 454-474. [21] C. Fournet, J.-J. Levy, A. Schmitt, An asynchronous distributed implementation of mobile ambients, in: Proceedings of IFIP-TCS, vol. 1872 of LNCS, Springer, 2000, pp. 348-364. · Zbl 0998.68537 [22] Gelernter, D., Generative communication in linda, ACM transactions on programming languages and systems, 7, 1, 80-112, (1985) · Zbl 0559.68030 [23] D. Gorla, On the relative expressive power of asynchronous communication primitives, in: Proceedings of FoSSaCS’06, vol. 3921 of LNCS, Springer, 2006. pp. 47-62. · Zbl 1180.68190 [24] D. Gorla, Synchrony vs asynchrony in communication primitives, in: Proceedings of EXPRESS’06, ENTCS, vol. 175, no. 3, Elsevier, 2007, pp. 87-108. · Zbl 1277.68185 [25] Herlihy, M., Wait-free synchronization, ACM transactions on programming languages and systems, 13, 1, 24-149, (1991) [26] K. Honda, M. Tokoro, An object calculus for asynchronous communication, in: Proceedings of ECOOP ’91, vol. 512 of LNCS, Springer, 1991, pp. 133-147. [27] Honda, K.; Yoshida, N., On reduction-based process semantics, Theoretical computer science, 152, 2, 437-486, (1995) · Zbl 0871.68122 [28] Milner, R., Communication and concurrency, (1989), Prentice Hall · Zbl 0683.68008 [29] R. Milner, The polyadic π-calculus: a tutorial, in: Logic and Algebra of Specification, vol. 94 of Series F. NATO ASI, Springer, 1993. [30] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, I and II, Information and computation, 100, 1, 1-40, (1992), 41-77 · Zbl 0752.68036 [31] R. Milner, D. Sangiorgi, Barbed bisimulation, in: Proceedings of ICALP ’92, vol. 623 of LNCS, Springer, 1992, pp. 685-695. [32] Nestmann, U., What is a ‘good’ encoding of guarded choice?, Information and computation, 156, 287-319, (2000) · Zbl 1046.68625 [33] U. Nestmann, Welcome to the jungle: a subjective guide to mobile process calculi (Invited Tutorial), in: Proceedings of CONCUR, vol. 4137 of LNCS, Springer, 2006, pp. 52-63. · Zbl 1151.68548 [34] Nestmann, U.; Pierce, B.C., Decoding choice encodings, Information and computation, 163, 1-59, (2000) · Zbl 1003.68080 [35] Palamidessi, C., Comparing the expressive power of the synchronous and the asynchronous π-calculi, Mathematical structures in computer science, 13, 5, 685-719, (2003) [36] J. Parrow, An introduction to the pi-calculus, in: Handbook of Process Algebra, Elsevier Science, 2001. pp. 479-543. · Zbl 1035.68071 [37] J. Parrow, Expressiveness of process algebras, in: LIX Colloquium on Emerging Trends in Concurrency Theory, ENTCS, 209 (2008) 173-186. [38] A. Phillips, N. Yoshida, S. Eisenbach, A distributed abstract machine for boxed ambient calculi, in: Proceedings of ESOP, vol. 2986 of LNCS, Springer, 2004, pp. 155-170. · Zbl 1126.68507 [39] I.C.C. Phillips, M.G. Vigliotti, Electoral systems in ambient calculi, in: Proceedings FoSSaCS, vol. 2987 of LNCS, 2004, pp. 408-422. · Zbl 1126.68508 [40] B.C. Pierce, D.N. Turner, Pict: a programming language based on the pi-calculus, in: Proof, Language and Interaction: Essays in Honour of Robin Milner, Foundations of Computing, MIT Press, May 2000. [41] P. Quaglia, D. Walker, On synchronous and asynchronous mobile processes, in: Proceedings of FoSSaCS 2000, vol. 1784 of LNCS, Springer, 2000, pp. 283-296. · Zbl 0961.68092 [42] Quaglia, P.; Walker, D., Types and full abstraction for polyadic π, Information and computation, 200, 2, 215-246, (2005) · Zbl 1101.68062 [43] Sangiorgi, D., Bisimulation in higher-order process calculi, Information and computation, 131, 141-178, (1996) · Zbl 0876.68042 [44] D. Sangiorgi, A. Valente, A distributed abstract machine for safe ambients, in: Proceedings of ICALP, vol. 2076 of LNCS, Springer, 2001, pp. 408-420. · Zbl 0986.68511 [45] Sangiorgi, D.; Walker, D., The π-calculus: A theory of mobile processes, (2001), Cambridge University Press · Zbl 0981.68116 [46] E.Y. Shapiro, Separating concurrent languages with categories of language embeddings, in: Proceedings of 23rd Symposium on Theory of Computing, ACM Press, 1991, pp. 198-208. [47] V. Vasconcelos, K. Honda, Principal typing schemes in a polyadic π-calculus, in: Proceedings of CONCUR’93, vol. 715 of LNCS, Springer, 1993, pp. 524-538. [48] N. Yoshida, Graph types for monadic mobile processes, in: Proceedings of FSTTCS ’96, vol. 1180 of LNCS, pp. 371-386. Springer, 1996. [49] G. Zavattaro, Towards a hierarchy of negative test operators for generative communication, in: Proc. of EXPRESS, ENTCS, vol. 16, no. 2, Elsevier, 1998, 154-170. · Zbl 0917.68073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.