×

On the expressive power of polyadic synchronisation in \(\pi \)-calculus. (English) Zbl 1270.68208

Nestmann, Uwe (ed.) et al., EXPRESS’02. Papers from the 9th international workshop on expressiveness in concurrency, Brno, Czech Republic, August 19, 2002. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 68, No. 2, 15-32 (2002).
Summary: We extend the \(\pi \)-calculus with polyadic synchronisation, a generalisation of the communication mechanism which allows channel names to be composite. We show that this operator embeds nicely in the theory of \(\pi \)-calculus, and makes it possible to derive divergence-free encodings of distributed calculi. We give a separation result between the \(\pi \)-calculus with polyadic synchronisation (\(^{e}\pi \)) and the original calculus, in the style of an analogous result given by Palamidessi for mixed choice. We encode local area \(\pi \) showing how to control the local use of resources in \(^{e}\pi \).
For the entire collection see [Zbl 1267.68026].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abadi, M.; Gordon, A. D., A calculus for cryptographic protocols: The spi calculus, (Research Report 149, DEC SRC (1998), a shortened version of this report appeared in Information and Computation 148 (1999)), 1-70 · Zbl 0924.68073
[2] Amadio, R.; Boudol, G.; Lousshaine, C., The receptive distributed pi-calculus, Proceedings of the 5th ECOOP Workshop on Mobile Object Systems (MOS’99) (1999), Lisbon: Lisbon Portugal
[3] Berger, M.; Honda, K., The two-phase commitment protocol in an extended pi-calculus, (Preliminary Proceedings of EXPRESS ’00, BRICS Notes Series, NS-00-2 (2000)), 105-130
[4] Boudol, G., Asynchrony and the π-calculus, Rapporte de Recherche 1702, INRIA Sofia-Antipolis (1992)
[5] Boudol, G.; Castellani, I., Concurrency and atomicity, (Theoretical Computer Science, 59 (1988)), 25-84 · Zbl 0678.68078
[6] Carbone, M.; Coccia, M.; Ferrari, G.; Maffeis, S., Process algebra-guided design of Java mobile network applications, Extended Abstract in Proc. of ECOOP’Ol Workshop on Formal Techniques for Java Programs (2001)
[7] Cardelli, L.; Gordon, A. D., Mobile ambients, (Theoretical Computer Science, 240 (2000)), 177-213, an extended abstract appeared in Proceedings of FoSSaCS ’98: 140155. · Zbl 0954.68108
[8] Chang, E. J.H.; Roberts, R., An improved algorithm for decentralized extrema-finding in circular configurations of processes, (Communications of the ACM, 22 (1979)), 281-283 · Zbl 0394.68023
[9] Chothia, T.; Stark, I., A distributed π-calculus with local areas of communication, (Proc. of HLCL ’00, ENTCS, 41.2 (2001)) · Zbl 1262.68137
[10] Chothia, T.; Stark, I., Encoding distributed areas and local communication into the pi-calculus, (Proc. of EXPRESS’Ol, ENTCS, 52.1 (2002)) · Zbl 1260.68260
[11] de Boer, F. S.; Palamidessi, C., Embedding as a tool for language comparison, (Information and Computation, 108 (1994)), 128-157 · Zbl 0788.68014
[12] Ferrari, G., Atomicity and concurrency control in process calculi, (FUNDINF: Fundamenta Informatica, 29 (1997)) · Zbl 0870.68067
[13] Fournet, C., ’The Join-Calculus: a Calculus for Distributed Mobile Programming,” Ph.D., thesis, Ecole Polytechnique (1998)
[14] Fournet, C.; Gonthier, G., The reflexive CHAM and the join-calculus, (Proceedings of the 23rd ACM Symposium on Principles of Programming Languages (1996)), 372-385
[15] Hennessy, M.; Riely, J., Resource access control in systems of mobile agents, (Proceedings of HLCL ’98, ENTCS, 16.3 (1998)), 3-17 · Zbl 0917.68047
[16] Honda, K.; Tokoro, M., On asynchronous communication semantics, (LNCS, 612 (1992)), 21-51
[17] Merro, M., On the expressiveness of chi, update, and fusion calculi, (EXPRESS ’98, ENTCS, 16.2 (1998)) · Zbl 0917.68071
[18] Merro, M., Locality and polyadicity in asynchronous name-passing calculi, (LNCS, 1784 (2000)), 238-251 · Zbl 0961.68091
[19] Merro, M.; Sangiorgi, D., On asynchrony in name-passing calculi, (LNCS, 1443 (1998)), 856-867 · Zbl 0910.03019
[20] Milner, R., ’Communication and Concurrency,” Prentice Hall (1989) · Zbl 0683.68008
[21] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, I and II, (Information and Computation, 100 (1992)), 1-40, 41-77 · Zbl 0752.68036
[22] Milner, R., Commitment and the polynomial pi-calculus, Talk at “What Good Are Partial Orders?” CALIBAN’92 Workshop, Sheffield (1992)
[23] Nestmann, U., On the expressive power of Joint Input, (EXPRESS ’98: Expressiveness in Concurrency (Nice, France, September 7, 1998), ENTCS, 16.2 (1998)) · Zbl 0917.68070
[24] Nestmann, U.; Pierce, B. C., Decoding choice encodings, (Journal of Information and Computation, 163 (2000)), 1-59 · Zbl 1003.68080
[25] Palamidessi, C., Comparing the expressive power of the synchronous and the asynchronous π-calculus, (Conference record of POPL ’97 (1997)), 256-265
[26] Ravara, A.; Vasconcelos, V. T., Typing non-uniform concurrent objects, (CONCUR’OO, LNCS 1877 (2000), Springer-Verlag), 474-488 · Zbl 0999.68151
[27] Sangiorgi, D., Lazy functions and mobile processes, Proof, Language and Interaction: Essays in Honour of Robin Milner (2000)
[28] Sangiorgi, D.; Walker, D., ’The π-calculus: a Theory of Mobile Processes,” (2001), Cambridge University Press · Zbl 0981.68116
[29] Sewell, P.; Wojciechowski, P.; Pierce, B., Location independence for mobile agents, (Proceedings of ICCL ’98, LNCS, 1686 (1999))
[30] Vasconcelos, V. T., “A Process-Calculus Approach to Typed Concurrent Objects,” Ph.D. thesis, Keio University (1994)
[31] Vasconcelos, V. T.; Tokoro, M., A typing system for a calculus of objects, (Object Technologies for Advanced Software,LNCS, 742 (1993), Springer-Verlag), 460-174
[32] Vivas Frontana, J.L. “Dynamic Binding of Names in Calculi for Mobile Processes,” Ph.D. thesis, Department of Microelectronics and Information Technology, Stockholm 2001; Vivas Frontana, J.L. “Dynamic Binding of Names in Calculi for Mobile Processes,” Ph.D. thesis, Department of Microelectronics and Information Technology, Stockholm 2001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.