zbMATH — the first resource for mathematics

Leader election in rings of ambient processes. (English) Zbl 1092.68068
Summary: Palamidessi has shown that the \(\pi\)-calculus with mixed choice is powerful enough to solve the leader election problem on a symmetric ring of processes. We show that this is also possible in the calculus of Mobile Ambients (MA), without using communication or restriction. Following Palamidessi’s methods, we deduce that there is no encoding satisfying certain conditions from MA into CCS. We also show that the calculus of Boxed Ambients is more expressive than its communication-free fragment.

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI
[1] D. Angluin, Local and global properties in networks of processors, in: Proc. 12th Annu. ACM Symp. on Theory of Computing, 1980, pp. 82-93.
[2] Bergstra, J.; Klop, J., Process algebra for synchronous communication, Inform. control, 60, 1-3, 109-137, (1984) · Zbl 0597.68027
[3] Boneva, I.; Talbot, J.-M., When ambients cannot be opened, Theoret. comput. sci., 333, 1-2, 127-169, (2005) · Zbl 1070.68042
[4] BougĂ©, L., On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes, Acta inform., 25, 179-201, (1988) · Zbl 0621.68011
[5] Bugliesi, M.; Castagna, G.; Crafa, S., Access control for mobile agents: the calculus of boxed ambients, ACM trans. program. lang. syst., 26, 1, 57-124, (2004)
[6] Cardelli, L.; Gordon, A., Mobile ambients, Theoret. comput. sci., 240, 1, 177-213, (2000) · Zbl 0954.68108
[7] Guan, X.; Yang, Y.; You, J., Making ambients more robust, (), 377-384
[8] Hoare, C., Communicating sequential processes, (1985), Prentice-Hall Englewood Cliffs · Zbl 0637.68007
[9] Levi, F.; Sangiorgi, D., Mobile safe ambients, ACM trans. program. lang. syst., 25, 1, 1-69, (2003)
[10] Maffeis, S.; Phillips, I., On the computational strength of pure ambient calculi, Theoret. comput. sci., 330, 3, 501-551, (2005) · Zbl 1078.68108
[11] M. Merro, M. Hennessy, A bisimulation-based semantic theory of safe ambients, ACM Trans. Program. Lang. Syst., 2006, in press. · Zbl 1323.68412
[12] Milner, R., Communication and concurrency, (1989), Prentice-Hall Englewood Cliffs · Zbl 0683.68008
[13] Milner, R., Communicating and mobile systems: the \(\pi\)-calculus, (1999), Cambridge University Press Cambridge, England · Zbl 0942.68002
[14] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, Inform. and comput., 100, 1-77, (1992) · Zbl 0752.68037
[15] Palamidessi, C., Comparing the expressive power of the synchronous and asynchronous \(\pi\)-calculi, Math. struct. comput. sci., 13, 5, 685-719, (2003)
[16] Phillips, I.; Vigliotti, M., On reduction semantics for the push and pull ambient calculus, (), 550-562
[17] I. Phillips, M. Vigliotti, Electoral systems in ambient calculi, in: Proc. 7th Internat. Conf. on Foundations of Software Science and Computation Structures, FoSSaCS 2004, Lecture Notes in Computer Science, Vol. 2987, Springer, Berlin, 2004, pp. 408-422. · Zbl 1126.68508
[18] I. Phillips, M. Vigliotti, Leader election in rings of ambient processes, in: Proc. Express: Workshop on Expressiveness in Concurrency, London, August 2004, Electronic Notes in Theoretical Computer Science, Vol. 128.2, Elsevier, New York, NY, 2005, pp. 185-199. · Zbl 1272.68318
[19] Sangiorgi, D., Pi-calculus, internal mobility and agent-passing calculi, Theoret. comput. sci., 167, 1-2, 235-274, (1996) · Zbl 0874.68103
[20] M. Vigliotti, Reduction semantics for ambient calculi, Ph.D. Thesis, Imperial College, University of London, 2004. · Zbl 1126.68508
[21] Zimmer, P., On the expressiveness of pure safe ambients, Math. struct. comput. sci., 13, 5, 721-770, (2003)
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.