AESOP home


Electoral systems in ambient calculi

Iain Phillips, Maria Vigliotti

Conference or Workshop Paper
7th International Conference on Foundations of Software Science and Computation Structures, Barcelona, Spain
Lecture Notes in Computer Science
Volume 2987
ISBN 3-540-21298-1
ISSN 0302-9743
DOI 10.1007/b95995

This paper compares the expressiveness of ambient calculi against different dialects of the pi-calculus. Cardelli and Gordon encoded the asynchronous pi-calculus into their calculus of Mobile Ambients (MA). Zimmer has shown that the synchronous pi-calculus without choice can be encoded in pure (no communication) Safe Ambients. We show that pure MA without restriction has symmetric electoral systems, that is, it is possible to solve the problem of electing a leader in a symmetric network. By the work of Palamidessi, this implies that pure MA without restriction is not encodable (under certain conditions) in the pi-calculus with separate choice. We adapt the work of Carbone and Maffeis to show that pure MA cannot be encoded (under certain other conditions) into the pi-calculus with mixed choice (but without matching).

Information from