Abstract
We present a novel approach to compare process calculi and their synchronisation mechanisms by using synchronisation patterns and explicitly considering the degree of distributability. For this, we propose a new quality criterion that (1) measures the preservation of distributability and (2) allows us to derive two synchronisation patterns that separate several variants of pi-like calculi. Precisely, we prove that there is no good and distributability-preserving encoding from the synchronous pi-calculus with mixed choice into its fragment with only separate choice, and neither from the asynchronous pi-calculus (without choice) into the join-calculus.
Supported by the DFG (German Research Foundation), grants NE-1505/2-1 and GO-671/6-1.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Berry, G., Boudol, G.: The Chemical Abstract Machine. In: Proc. of POPL. SIGPLAN-SIGACT, pp. 81–94 (1990)
Best, E., Darondeau, P.: Petri Net Distributability. In: Clarke, E., Virbitskaite, I., Voronkov, A. (eds.) PSI 2011. LNCS, vol. 7162, pp. 1–18. Springer, Heidelberg (2012)
Boudol, G.: Asynchrony and the π-calculus (note). Note, INRIA (1992)
Cacciagrano, D., Corradini, F., Palamidessi, C.: Explicit fairness in testing semantics. Logical Methods in Computer Science 5(2), 1–27 (2009)
Carbone, M., Maffeis, S.: On the Expressive Power of Polyadic Synchronisation in π-Calculus. Nordic Journal of Computing 10(2), 70–98 (2003)
Dijkstra, E.W.: Hierarchical Ordering of Sequential Processes. Acta Informatica 1(2), 115–138 (1971)
Fournet, C., Gonthier, G.: The Reflexive CHAM and the Join-Calculus. In: Proc. of POPL. SIGPLAN-SIGACT, pp. 372–385 (1996)
Gorla, D.: Towards a Unified Approach to Encodability and Separation Results for Process Calculi. Information and Computation 208(9), 1031–1053 (2010)
Hennessy, M.: A Distributed Pi-Calculus. Cambridge University Press (2007)
Honda, K., Tokoro, M.: An Object Calculus for Asynchronous Communication. In: America, P. (ed.) ECOOP 1991. LNCS, vol. 512, pp. 133–147. Springer, Heidelberg (1991)
Laneve, C., Vitale, A.: The Expressive Power of Synchronizations. In: Proc. of LICS, pp. 382–391 (2010)
Lévy, J.-J.: Some Results in the Join-Calculus. In: Ito, T., Abadi, M. (eds.) TACS 1997. LNCS, vol. 1281, pp. 233–249. Springer, Heidelberg (1997)
Milner, R.: Communicating and Mobile Systems: The π-Calculus. Cambridge University Press, New York (1999)
Milner, R., Parrow, J., Walker, D.: A Calculus of Mobile Processes, Part I and II. Information and Computation 100(1), 1–77 (1992)
Milner, R., Sangiorgi, D.: Barbed Bisimulation. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 685–695. Springer, Heidelberg (1992)
Nestmann, U.: What is a “Good” Encoding of Guarded Choice? Information and Computation 156(1-2), 287–319 (2000)
Palamidessi, C.: Comparing the Expressive Power of the Synchronous and the Asynchronous π-calculus. Mathematical Structures in Computer Science 13(5), 685–719 (2003)
Peters, K.: Translational Expressiveness. PhD thesis, TU Berlin (2012), http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-37495
Peters, K., Nestmann, U.: Is It a “Good” Encoding of Mixed Choice? In: Birkedal, L. (ed.) FOSSACS 2012. LNCS, vol. 7213, pp. 210–224. Springer, Heidelberg (2012)
Peters, K., Nestmann, U., Goltz, U.: On Distributability in Process Calculi (Appendix). Technical Report, TU Berlin (2013), http://www.mtv.tu-berlin.de/fileadmin/a3435/pubs/distProcCal.pdf
Peters, K., Schicke-Uffmann, J.-W., Nestmann, U.: Synchrony vs Causality in the Asynchronous Pi-Calculus. In: Proc. of EXPRESS. EPTCS, vol. 64, pp. 89–103 (2011)
Plotkin, G.D.: A structural approach to operational semantics. Journal of Logic and Algebraic Programming 60, 17–140 (2004); (An earlier version of this paper was published as technical report at Aarhus University in 1981)
van Glabbeek, R.: The Linear Time – Branching Time Spectrum I: The Semantics of Concrete, Sequential Processes. Handbook of Process Algebra, 3–99 (2001)
van Glabbeek, R., Goltz, U., Schicke, J.-W.: On Synchronous and Asynchronous Interaction in Distributed Systems. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 16–35. Springer, Heidelberg (2008)
van Glabbeek, R., Goltz, U., Schicke-Uffmann, J.-W.: On Distributability of Petri Nets. In: Birkedal, L. (ed.) FOSSACS 2012. LNCS, vol. 7213, pp. 331–345. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peters, K., Nestmann, U., Goltz, U. (2013). On Distributability in Process Calculi. In: Felleisen, M., Gardner, P. (eds) Programming Languages and Systems. ESOP 2013. Lecture Notes in Computer Science, vol 7792. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37036-6_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-37036-6_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37035-9
Online ISBN: 978-3-642-37036-6
eBook Packages: Computer ScienceComputer Science (R0)