Comparing the expressive power of the synchronous and the asynchronous π-calculus

The Asynchronous ¿-calculus, as recently proposed by Boudol and, independently, by Honda and Tokoro, is a subset of the ¿-calculus which contains no explicit operators for choice and output-prefixing. The communication mechanism of this calculus, however, is powerful enough to simulate output-prefixing, as shown by Boudol, and input-guarded choice, as shown recently by Nestmann and Pierce. A natural question arises, then, whether or not it is possible to embed in it the full ¿-calculus. We show that this is not possible, i.e. there does not exist any uniform, parallel-preserving, translation from the ¿-calculus into the asynchronous ¿-calculus, up to any "reasonable" notion of equivalence. This result is based on the incapablity of the asynchronous ¿-calculus of breaking certain symmetries possibly present in the initial communication graph. By similar arguments, we prove a separation result between the ¿-calculus and CCS.

• Publication year

  1998

• Venue

  ACM-SIGACT Symposium on Principles of Programming Languages

• Publication date

  1998-09-02

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/263699.263731arXiv cs/9809008
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Theories of Programming Languages: Communicating Sequential Processes

  1998cited by this paper
• Some Congruence Properties for Pi-Calculus Bisimilarities

  1998cited by this paper
• What is a 'good' encoding of guarded choice?

  1997cited by this paper
• pi-Calculus, Internal Mobility, and Agent-Passing Calculi

  1996cited by this paper
• Decoding Choice Encodings

  1996cited by this paper
• On the Expressiveness of Internal Mobility in Name-Passing Calculi

  1996cited by this paper
• - calculus , internal mobility , and agent-passing calculi

  1995cited by this paper
• The Polyadic π-Calculus: a Tutorial

  1993cited by this paper
• A Calculus of Mobile Processes, II

  1992cited by this paper
• Multiway Synchronization Verified with Coupled Simulation

  1992influential reference
• An Object Calculus for Asynchronous Communication

  1991cited by this paper
• On Asynchronous Communication Semantics

  1991cited by this paper
• Modal Logics for Mobile Processes

  1991cited by this paper
• A Theory of Synchrony and Asynchrony

  1990cited by this paper
• A Calculus of Mobile Processes, Part Ii

  1989cited by this paper
• A Calculus of Mobile Processes, Part I

  1989cited by this paper
• Communication and concurrency

  1989influential reference
• On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes

  1988influential reference
• On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes

  1988cited by this paper
• Process Algebra with Asynchronous Communication Mechanisms

  1984cited by this paper
• A distributed abstract data type implemented by a probabilistic communication scheme

  1980cited by this paper

• Mixed choice in session types

  2024cites this paper
• Book review

  2022cites this paper
• On the Expressiveness of Mixed Choice Sessions (Technical Report)

  2022influential citation
• Team Comète Concurrence , Mobilité et Transactions

  2022cites this paper
• Minimal Translations from Synchronous Communication to Synchronizing Locks (Extended Version)

  2021cites this paper
• Ready, set, Go!: Data-race detection and the Go language

  2020cites this paper
• Correctly Implementing Synchronous Message Passing in the Pi-Calculus By Concurrent Haskell's MVars

  2020cites this paper
• On the Interactive Power of Higher-order Processes Extended with Parameterization

  2020cites this paper
• Comparing Process Calculi Using Encodings

  2019cites this paper
• Psi-Calculi Revisited: Connectivity and Compositionality

  2019cites this paper
• Ready, set, Go! Data-race detection and the Go language

  2019cites this paper
• Polymorphic Session Processes as Morphisms

  2019cites this paper
• The Logic of Fault-Tolerance in Message-Passing Concurrency

  2019cites this paper
• A Fully Abstract Encoding for Sub Asynchronous Pi Calculus

  2018cites this paper
• Information and Computation

  2018cites this paper
• Formal Methods

  2018influential citation
• Operational Semantics of a Weak Memory Model with Channel Synchronization

  2018cites this paper
• An operational semantics for a weak memory model with buffered writes, message passing, and goroutines

  2017cites this paper
• The Universal Process

  2017influential citation
• Abstract Continuation Semantics for Asynchronous Concurrency

  2017cites this paper
• On parameterization of higher-order processes

  2017cites this paper
• The Expressive Power of Monotonic Parallel Composition

  2016influential citation
• Culling Concurrency Theory : Reusable and trustworthy meta-theory, proof techniques and separation results

  2016cites this paper
• Session Types for Link Failures (Technical Report)

  2016cites this paper
• Specification and analysis of service oriented architectures within the calculus of communicating sequential processes (CSP)

  2016cites this paper
• Theory of interaction

  2016influential citation
• On the expressiveness of π-calculus for encoding mobile ambients

  2016cites this paper
• The Name-Passing Calculus

  2015cites this paper
• Higher-order languages : dualities and bisimulation enhancements. (Langages d'ordre supérieur : dualités et techniques de bisimulation)

  2015cites this paper
• Observational program calculi and the correctness of translations

  2015cites this paper
• Matching in the Pi-Calculus (Technical Report)

  2014cites this paper
• Expressiveness via Intensionality and Concurrency

  2014cites this paper
• Process Cooperativity as a Feedback Metric in Concurrent Message-Passing Languages

  2014cites this paper
• Matching in the Pi-Calculus

  2014cites this paper
• Continuation Semantics for Asynchronous Concurrency

  2014cites this paper
• Synchrony versus causality in distributed systems †

  2014cites this paper
• The Value-Passing Calculus

  2013cites this paper
• From Computing to Interaction: on the Expressiveness of Asynchronous pi-Calculus

  2013cites this paper
• How faithfully can π be interpreted in SA?

  2013cites this paper
• Continuation Semantics for Asynchronous Concurrency by

  2013cites this paper
• The Concurrency Column

  2013cites this paper
• On the Expressiveness of Parameterization in Process-Passing

  2013cites this paper
• On Characterising Distributability

  2013cites this paper
• Concurrency in Interaction Nets and Graph Rewriting

  2013influential citation
• On Distributability in Process Calculi

  2013influential citation
• Expressing global priorities by best-matching

  2012cites this paper
• Abstract Continuation Semantics for Asynchronous Concurrency by

  2012cites this paper
• Process Algebras for Locality

  2012cites this paper
• Is it a "Good" Encoding of Mixed Choice? (Technical Report)

  2012cites this paper
• Translational Expressiveness. Comparing Process Calculi using Encodings

  2012cites this paper
• Distinguishing and relating higher-order and first-order processes by expressiveness

  2012cites this paper
• Design, Modelling and Analysis of a Workflow Reconfiguration

  2011cites this paper
• A Case Study of Workow Reconguration: Design and Implementation

  2011cites this paper
• Synchrony vs Causality in the Asynchronous Pi-Calculus

  2011cites this paper
• A Case Study of Workflow Reconfiguration: Design, Modelling, Analysis and Implementation

  2011cites this paper
• Toward Design, Modelling and Analysis of Dynamic Workflow Reconfigurations - A Process Algebra Perspective

  2011cites this paper
• Formal Modeling and Simulation of Biological Systems with Delays

  2011cites this paper
• On the expressiveness of interaction

  2010influential citation
• A taxonomy of process calculi for distribution and mobility

  2010cites this paper
• Breaking symmetries †

  2010cites this paper
• Nomadic pict: Programming languages, communication infrastructure overlays, and semantics for mobile computation

  2010influential citation
• On the Expressive Power of Primitives for Compensation Handling

  2010cites this paper
• On Mobility and Communication

  2010cites this paper
• Process Models for Distributed Event-Based Systems

  2010cites this paper
• Stochastic biological modelling in the presence of multiple compartments

  2009cites this paper
• Asynchronous Process Calculi for Specification and Verification of Information Hiding Protocols

  2009cites this paper
• Probabilistic and nondeterministic aspects of anonymity

  2009cites this paper
• Calculs de processus: observations et inspections. (Process calculi: observations, inspections)

  2009cites this paper
• Explicit fairness in testing semantics

  2009cites this paper
• On the expressive power of process interruption and compensation

  2009cites this paper
• An expressiveness study of priority in process calculi

  2009cites this paper
• Trading Off Concurrency to Generate Behavioral Adapters

  2009cites this paper
• What’s TyCO, After All?

  2009cites this paper
• On Synchronous and Asynchronous Interaction in Distributed Systems

  2008cites this paper
• Semantics of Higher-Order Mobile Embedded Resources and Local Names

  2008cites this paper
• Model-based integration and testing of high-tech multi-disciplinary systems

  2008cites this paper
• Towards a unified approach to encodability and separation results for process calculi

  2008influential citation
• Computational self-assembly

  2008cites this paper
• Coordination Models Orc and Reo Compared

  2008cites this paper
• Election and rendezvous with incomparable labels

  2008cites this paper
• Free-algebra models for the pi -calculus

  2008cites this paper
• A process algebraic view of shared dataspace coordination

  2008cites this paper
• Modelling and simulation of dynamic structure discrete-event systems

  2008cites this paper
• Symmetric and Asymmetric Asynchronous Interaction

  2008cites this paper
• Comparing communication primitives via their relative expressive power

  2008influential citation
• Symmetric electoral systems for ambient calculi

  2008cites this paper
• On the Asynchronous Nature of the Asynchronous pi-Calculus

  2008influential citation
• Expressiveness of Process Algebras

  2008cites this paper
• ICE 2008 Symmetric and Asymmetric Asynchronous Interaction

  2008cites this paper
• Verification of Peer-to-peer Algorithms: A Case Study

  2007cites this paper
• Linearity, Persistence and Testing Semantics in the Asynchronous Pi-Calculus

  2007cites this paper
• L  C

  2007cites this paper
• A Note on Scope and Infinite Behaviour in CCS-like Calculi

  2007cites this paper
• Quantum Programming Language LanQ

  2007cites this paper
• Behavioral complexity indicators for process algebra: The NKS approach

  2007cites this paper
• Modeling, analysis, and implementation of infrastructure for model-based integration and testing

  2007cites this paper
• Tutorial on separation results in process calculi via leader election problems

  2007influential citation
• A Core Calculus for a Comparative Analysis of Bio-inspired Calculi

  2007cites this paper
• Classifying Interactions via Subbisimilarity

  2007influential citation
• A typed encoding of boxed into safe ambients

  2006cites this paper