Skip to Main content Skip to Navigation
Journal articles

A randomized encoding of the pi-calculus with mixed choice

Catuscia Palamidessi 1 Oltea Mihaela Herescu 2
1 COMETE - Concurrency, Mobility and Transactions
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : We consider the problem of encoding the pi-calculus with mixed choice into the asynchronous pi-calculus via a uniform translation while 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 pi-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 it is robust to attacks of proper adversaries.
Document type :
Journal articles
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/inria-00201105
Contributor : Catuscia Palamidessi <>
Submitted on : Sunday, December 23, 2007 - 6:18:20 PM
Last modification on : Thursday, March 5, 2020 - 6:18:32 PM
Long-term archiving on: : Tuesday, April 13, 2010 - 3:32:30 PM

File

report.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Catuscia Palamidessi, Oltea Mihaela Herescu. A randomized encoding of the pi-calculus with mixed choice. Theoretical Computer Science, Elsevier, 2005, 335 (2-3), pp.373-404. ⟨10.1016/j.tcs.2004.11.020⟩. ⟨inria-00201105⟩

Share

Metrics

Record views

567

Files downloads

297