Series: Logic Seminar

Date: Tuesday, April 7, 1998

Time: 2:30 PM

Place: 308 Boucke Building

Title: Communication and Choice in Mobile Networks
 
Speaker:  Catuscia Palamidessi (Penn State CSE)
 
Abstract:

The Pi-Calculus is an extension of Milner's CCS (Calculus for
Communicating Systems) with mechanisms for Mobility, i.e. mechanisms
which allow process migration and reconfiguration of of the connection
topology.  Several variants of this calculus have been developed for
specific applications, and, surprisingly enough, most of them have
been proved equivalent from the point of view of expressiveness. The
reason seems to lay in the fact that the core pi-calculus has an
extremely powerful mechanism for dealing with mobility of links.
 
In this talk we focus on the Asynchronous Pi-Calculus, the sublanguage
with no constructs for synchronous output and choice.  It has been
shown that both synchronous communication and input-guarded choice can
be simulated in the Asynchronous Pi-Calculus, and an implementation of
it has been developed (by Benjamin Pierce, at Indiana University). A
natural question is, then, whether or not it is possible to embed in
it the full Pi-Calculus.  We show that it is not possible, i.e. there
does not exists any uniform, parallel preserving, translation from the
Pi-Calculus into the Asynchronous Pi-Calculus, up to any "reasonable"
notion of equivalence. This result is based on the impossibility of
the Asynchronous Pi-Calculus to break certain symmetries possibly
present in the initial state of the network. By a similar argument, we
prove a separation result between the Pi-Calculus and the subset
without mobility (or with "internal" mobility only).