CS Paper Radar

On Asynchrony and Reversibility in CCS

Hernán Melgratti, Claudio Antares Mezzina, G. Michele Pinna

cs.LO cs.FLcs.PL ·submitted 2026-09-28 11:25 UTC · v1
published

Abstract

Asynchronous communication is a fundamental feature of modern distributed systems, where messages are emitted without requiring immediate synchronization with receivers. In process calculi, this behaviour is typically modelled by separating message emission from message consumption. At the same time, reversible computation has emerged as an important paradigm for analysing concurrent systems, enabling computations to be undone while preserving causal dependencies between actions. While reversible semantics have been extensively studied for synchronous process calculi such as CCS, their integration with asynchronous communication remains largely unexplored. In this paper we investigate the interaction between asynchrony and reversibility in the setting of CCS. We first introduce CCSa, an asynchronous variant of CCS in which output actions generate explicit message entities that can later be consumed by matching input actions. We then define rCCSa, a reversible extension of CCSa obtained by adapting the framework of Phillips and Ulidowski. In rCCSa, prefixes and messages are annotated with unique keys that record message emission and consumption events, allowing computations to be reversed while preserving causal dependencies. We show that the resulting reversible semantics satisfies causal consistency, ensuring that computations can be reversed exactly up to causal equivalence. The proof relies on the axiomatic framework for reversible computation proposed by Lanese et al.

Comment
In Proceedings ICE 2026, arXiv:2609.30353
Journal ref
EPTCS 453, 2026, pp. 23-39
DOI
10.4204/EPTCS.453.3

Closest papers

Nearest neighbours by meaning across the whole index.

Transition Systems from Causal Reversible Bundle Event Structures

cs.GT ·2026-08-25 ·Nataliya Gribovskaya, Irina Virbitskaite
published similarity 0.71
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Reversible computing is a novel paradigm that has recently emerged and extends traditional forwards-only computation with the capability to execute in the reverse direction, making it possible for computation to run backwards as well as forwards. Event structures are a foundational model in concurrency theory, providing a way to understand computational processes by describing the events that occur and the relationships between them. In the literature, two structurally different approaches to associating transition system semantics with event structure models have been distinguished. One approach is based on configurations, which are sets of already executed events. The other approach is based on model residuals, which are not yet executed fragments of the model. Configuration-based transition systems appear to be primarily used for semantic representations. Residual-based transition systems are actively applied to demonstrate the consistency between operational and denotational semantics of concurrent process calculi, as well as to visualize the dynamics of models. The present paper focuses on bundle event structures with causal reversibility, which are used in the study of reversible extensions of CCS- and π-like systems. Mappings from the reversible event structure model to the two transition system semantics are developed, which made it possible to prove the isomorphism of the semantics. A category-theoretic characterization of the mappings is provided.

0.43

Concurrency, Causality and Conflict via Independence in Reversible Calculi

cs.LO ·2026-09-16 ·Clément Aubert, Gabriele Cecilia, Iain C. C. Phillips, Irek Ulidowski
theory similarity 0.67
Abstract · 45 pages, 18 figures

Among the different ways of approaching the semantics of process calculi, true-concurrency models stand out for their ability to highlight subtle interplays between events. At their heart lie three crucial relations: concurrency, causality and conflict. This paper shows that reversibility, when endowed with a notion of independence, provides a rich tooling to study and characterise these true-concurrency relations. First, we prove that systems admitting pre-reversibility (i.e., that can be extended with an independence relation satisfying some basic axioms) have a unique notion of independence, events, concurrency, causality and conflict. We then analyse the relationship between independence and the true-concurrency relations, establishing novel independence-based characterisations of causality and conflict. Our second series of contributions revolves around two concrete process calculi and two syntactic notions defined on their transition labels, namely independence and dependence; we prove that they partition connected transitions and characterise elegantly concurrency on adjacent transitions. This part of our development was machine-checked using the proof assistant Beluga. Last, we study how the key mechanism commonly used in reversible process algebra can be used as a proxy to retrieve causality and core independence on past events. We conclude by discussing how our results extend beyond reversible systems.

0.25

Fine-grained Causal Reversibility for Asynchronous Channel-based Programming

cs.PL ·2026-08-29 ·Shunya Oguchi, Shoji Yuen, Nobuko Yoshida, Claudio Antares Mezzina
published similarity 0.63
Abstract · 33 pages, 10 figures. Extended version of the paper accepted at ICTAC 2026. This version includes complete proofs and additional technical m…

Causal reversibility has emerged as an effective technique for debugging concurrent systems. In particular, rolling back and replaying a concurrent program with causal consistency has been found very helpful in debugging concurrency bugs. In channel-based communication, queue ordering creates dependencies that prevent causally independent actions from being rolled back and replayed. To enable efficient rollback and replay without being constrained by queue dependencies, it is necessary to analyse causal dependencies between messages in queues and reorder independent messages. This paper presents revGo, a core of the Go programming language assuming unbounded asynchronous channels. Our rollback-and-replay semantics allows us to reorder messages in the queue if they are not causally related in the forward execution. It is shown that reordering independent messages generates no configuration with non-reachable processes. By reordering independent messages, rollback and replay are implementable with minimality by assigning unique keys to communications.

0.40

Coexponential Exploration in the Clef Programming Language

cs.PL cs.DCcs.LO ·2026-10-09 ·Houston Haynes
theory similarity 0.62
Abstract · 36 pages, 4 figures, 3 tables. Updated for contributions from Karwowski et al. and clarified Padovani's fair-termination result

Clef was created as a concurrent programming language whose compiler tracks state ownership, waiting computations and request dependencies. We develop a coexponential account of stateful services and their client pools within this design. Delimited continuations retain the computation and resources needed to complete each interaction. These structures give our compiler premises for verifying service composition and preserving it through native lowering to multiple hardware targets. We connect finite actor state transitions to the initial, service and final rules of a coexponential server. A separate operational account relates actor dispatch to single-use continuation frames. We prove state-ownership and reply preservation, give a finite communication-summary analysis, and derive circular-wait exclusion under stated assumptions. A further result identifies when changing service order preserves both state and replies. Our Program Semantic Graph retains these facts through compilation. We are researching reusable proofs to confirm the ownership and communication interfaces, while our BAREWire implementation connects message meaning to its unboxed representation across respective endpoints. A distributed worker example preserves request identity across suspension, reordered replies and boundary conversion. Urschel's growth bounds inform a solver service; a distributed ADM update additionally preserves joint samples, metric evidence and request identity. Our two-category account connects component refinement, reusable proof terms and native realization. Protocols determine the admissible interactions, continuations expose their storage requirements, and retained dependencies support differential compilation. Developers can express ordinary stateful services while the compiler carries the conditions for their correct composition across execution targets.

0.19

A Principled Approach to Concurrency, Nondeterminism, and Asynchrony in Choreographies

cs.PL ·2026-11-18 ·Xueying Qin, Marco Peressotti, Fabrizio Montesi
theory similarity 0.61
Abstract · 31 pages including appendix

Choreographic programming (CP) describes a distributed system as a global program and compiles it into communicating network programs via endpoint projection (EPP). Asynchrony captures the independent progress of communicating processes, while nondeterminism captures the range of behaviours that can arise from their interactions. However, the integration of both features into a theory of CP is absent. We present Nyarlathotep, the first asynchronous nondeterministic CP framework. We define its operational semantics of choreographies and networks using labelled transition systems. Besides asynchrony and choreographic nondeterminism, Nyarlathotep supports expressive features including general branching, out-of-order execution, and general recursion with parameterised procedures that processes can enter independently. We prove EPP sound and complete, establishing strong behavioural equivalence between the semantics of choreographies and their projected networks. We prove that projected networks are communication-safe and deadlock-free. We mechanised all our results in Lean 4.

0.16

On the Expressiveness of Asynchronous Processes with Nested Session Types (Extended Version)

cs.PL cs.DC ·2026-10-23 ·Sjors Wortelboer, Dan Frumin, Jorge A. Pérez
theory similarity 0.60
Abstract · Extended version of a paper submitted to EXPRESS/SOS 2026

Session types are a type-based approach to correct message-passing programs, where types specify protocols for channels and type checking guarantees communication correctness. Traditional session types express regular protocols only, which leaves out many protocols found in practice. Aiming at overcoming this limitation, Nested Session Types (NSTs) can specify nested recursive protocols. NSTs are known to be characterised by one-counter machines and deterministic context-free languages. In this paper, we study the expressiveness of ASP (Asynchronous Session Processes), the process model associated with NSTs as introduced by Das et al. We prove that AST is Turing complete by giving a correct encoding of two-counter machines into typed processes. Our encoding uses a non-trivial state-aware representation of counters and instructions that is neatly governed by NSTs.

0.34

Episodic Loops: Finitary Event Structures and Operational Semantics for C11 Programs with Retries

cs.PL ·2026-09-28 ·Christian Kissig, Jay Richards, Mark Batty
code/data similarity 0.58
Abstract · 115 pages (42 pages main text plus appendices), 19 figures, 2 tables. Reference implementation: https://github.com/christiankissig/mordor ; …

Lock-free synchronisation algorithms are often implemented with fallible operations, such as compare-and-swap (CAS), wrapped in unbounded retry loops. Verifying such algorithms requires considering arbitrarily many failing iterations, yielding large state spaces, compounded by the interleavings of concurrent threads. Prior work discarded failing iterations, arguing that they leave no trace in the post-loop state. Compilers and hardware reorder instructions, and load-store reorderings may cross the boundaries of failing iterations, introducing subtle concurrency bugs. We demonstrate one such bug, making use-after-free possible in a previously verified variant of Read-Copy-Update - a synchronisation primitive widely adopted in the Linux Kernel - and we provide and verify a fix. We find that practical retries in lock-free algorithms adhere to a common pattern. We introduce episodic loops, a semantic characterisation of unbounded retry loops which is syntactically recognisable in many practical cases, and synchronisation points, operations that bound both instruction reordering and state space within episodic loops. We show that SMRD - a symbolic event structure semantics for C11 programs which allows for load-store reordering - admits a finite representation in programs where unbounded loops are episodic. We further introduce a finitary operational semantics that allows safety properties to be verified in finitely many steps. For the use-after-free bug we demonstrate, verification takes a single pass over the program, linear in the program size. We provide a reference implementation of SMRD reproducing the bug and verifying the fix, and mechanise the operational semantics together with the minimal bug and its fix in Isabelle/HOL.

0.38

Substep Linearizability: Relaxing Atomicity While Preserving Sequential Specification

cs.DC ·2026-10-12 ·Finn Hackett, Evan Wrench, Ivan Beschastnikh, Yuanhao Wei
similarity 0.57
Abstract

Linearizability is a standard correctness condition for concurrent objects. It takes a correct by construction sequential specification of a concurrent data structure, and produces a composable specification under atomic interleavings of operations. However, some operations like atomic exchangers are not specifiable atomically, making it difficult to reason compositionally about their specifications. Interval linearizability is the state of the art in relaxing linearizability's constraints. Formally it is a powerful framework, but it requires an interval-sequential specification of the target data structure, which we show is challenging to correctly generate or understand, even for simple operations on a single concurrent register. We propose substep linearizability, which we show is equivalent to interval linearizability using X-CCorrectness, a relaxed concurrency framework we created to compare existing linearizability semantics. We show that substep linearizability's sequential specifications are suitable for previously infeasible specification tasks, while being comparable in complexity to linearizability's sequential specifications. For evaluation, we model an atomic exchanger, a popular non-linearizable queue structure, and snapshot isolation between database transactions.

0.43