Skip to Main content Skip to Navigation
Book sections

On the asynchronous nature of the asynchronous π-calculus

Romain Beauxis 1 Catuscia Palamidessi 1 Frank Valencia 1
1 COMETE - Concurrency, Mobility and Transactions
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Document type :
Book sections
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Catuscia Palamidessi <>
Submitted on : Saturday, January 30, 2010 - 5:48:23 AM
Last modification on : Thursday, March 5, 2020 - 6:24:13 PM
Long-term archiving on: : Thursday, September 23, 2010 - 11:56:13 AM


Files produced by the author(s)




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⟩



Record views


Files downloads