A randomized encoding of the pi-calculus with mixed choice

Catuscia Palamidessi 1 Oltea Mihaela Herescu 2
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2005, 335 (2-3), pp.373-404. 〈10.1016/j.tcs.2004.11.020〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00201105
Contributeur : Catuscia Palamidessi <>
Soumis le : dimanche 23 décembre 2007 - 18:18:20
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : mardi 13 avril 2010 - 15:32:30

Fichier

report.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

468

Téléchargements de fichiers

225