About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theoretical Computer Science
Conference paper
A randomized encoding of the π-calculus with mixed choice
Abstract
We consider the problem of encoding the π-calculus with mixed choice (i.e. input/output guarded choice) into the asynchronous π-calculus. We are interested in a translation which satisfies certain desirable properties, namely uniformity and preservation of 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, unlike previous proposals in literature, does not rely on assumptions on the relative speed of processes and it is robust to attacks of proper adversaries. © 2005 Elsevier B.V. All rights reserved.