Synchrony vs Causality in the Asynchronous Pi-Calculus

Kirstin Peters
Jens-Wolfhard Schicke
Uwe Nestmann

We study the relation between process calculi that differ in their either synchronous or asynchronous interaction mechanism. Concretely, we are interested in the conditions under which synchronous interaction can be implemented using just asynchronous interactions in the pi-calculus. We assume a number of minimal conditions referring to the work of Gorla: a "good" encoding must be compositional and preserve and reflect computations, deadlocks, divergence, and success. Under these conditions, we show that it is not possible to encode synchronous interactions without introducing additional causal dependencies in the translation.

In Bas Luttik and Frank Valencia: Proceedings 18th International Workshop on Expressiveness in Concurrency (EXPRESS 2011), Aachen, Germany, 5th September 2011, Electronic Proceedings in Theoretical Computer Science 64, pp. 89–103.
Published: 20th August 2011.

ArXived at: http://dx.doi.org/10.4204/EPTCS.64.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org