On the asynchronous nature of the asynchronous π-calculus

Romain Beauxis 1 Catuscia Palamidessi 1 Frank Valencia 1
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 address the question of what kind of asynchronous com- munication is exactly modeled by the asynchronous pi-calculus (pi_a). To this purpose we define a calculus pi_B where channels are represented explicitly as special buffer processes. The base language for pi_B is the (synchronous) pi-calculus, except that ordinary processes communicate only via buffers. Then we compare this calculus with pi_a. It turns out that there is a strong correspondence between pi_a and pi_B in the case that buffers are bags: we can indeed encode each pi_a process into a strongly asynchronous bisimilar pi_B process, and each pi_B process into a weakly asynchronous bisimilar pi_a process. In case the buffers are queues or stacks, on the contrary, the correspondence does not hold. We show indeed that it is not possible to translate a stack or a queue into a weakly asynchronous bisimilar pi_a process. Actually, for stacks we show an even stronger result, namely that they cannot be encoded into weakly (asynchronous) bisimilar processes in a pi-calculus without mixed choice.
Type de document :
Chapitre d'ouvrage
Rocco De Nicola, Pierpaolo Degano, and José Meseguer. Concurrency, Graphs and Models, Springer, pp.473-492, 2008, Lecture Notes in Computer Science, 〈10.1007/978-3-540-68679-8_29〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00349226
Contributeur : Catuscia Palamidessi <>
Soumis le : samedi 30 janvier 2010 - 05:48:23
Dernière modification le : jeudi 12 avril 2018 - 01:47:14
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 11:56:13

Fichier

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

Identifiants

Collections

Citation

Romain Beauxis, Catuscia Palamidessi, Frank Valencia. On the asynchronous nature of the asynchronous π-calculus. Rocco De Nicola, Pierpaolo Degano, and José Meseguer. Concurrency, Graphs and Models, Springer, pp.473-492, 2008, Lecture Notes in Computer Science, 〈10.1007/978-3-540-68679-8_29〉. 〈inria-00349226v2〉

Partager

Métriques

Consultations de la notice

329

Téléchargements de fichiers

109