A Randomized Distributed Encoding of the π-Calculus with Mixed Choice
Catuscia Palamidessi, Oltea Mihaela Herescu · 2002
We consider the problem of encoding the π-calculus (more precisely, the version of the π-calculus with mixed choice) into the asynchronous π-calculus via a uniform translation preserving a reasonable semantics. Although it has been shown that this is not possible with an exact encoding, we suggest a randomized approach using a probabilistic extension of the asynchronousπ-calculus, and we show that our solution is correct with probability 1 under any proper adversary wrt a notion of testing semantics. This result establishes the basis for a distributed and symmetric implementation of mixed choice which, differently from previous proposals in literature, does not rely on assumptions on the relative speed of processes and is robust to attacks of proper adversaries. 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.