CS Paper Radar

Concurrency, Causality and Conflict via Independence in Reversible Calculi

Clément Aubert, Gabriele Cecilia, Iain C. C. Phillips, Irek Ulidowski

cs.LO ·submitted 2026-09-16 23:26 UTC · v1
theory

Abstract

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.

Comment
45 pages, 18 figures

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.78
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

On Asynchrony and Reversibility in CCS

cs.LO cs.FLcs.PL ·2026-09-28 ·Hernán Melgratti, Claudio Antares Mezzina, G. Michele Pinna
published similarity 0.67
Abstract · In Proceedings ICE 2026, arXiv:2609.30353

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.

0.31

String Diagrams for Process Mining

cs.LO cs.DBmath.CT ·2026-09-17 ·Antony R. Lee, Peter Tiňo, Iain B. Styles
similarity 0.60
Abstract · 67 pages, 22 figures, 4 tables

Run two process-discovery algorithms on the same event log and they return two different pictures of the same process. Petri nets, causal nets, process trees and BPMN each rely on routing machinery of their own, and their only common ground is the traces they generate. A trace lists activities one after another, so it discards the concurrency the notations exist to express, and two models with identical trace languages can describe genuinely different processes. Whether two discovered models mean the same thing therefore has no notation-independent answer. We show that all four notations admit one canonical presentation, a signature recording a model's activities and the typed interfaces along which they compose, and nothing of the routing machinery. Four construction theorems establish this presentation notation by notation, so two models are compared in a form that each notation determines on its own. Signature equality implies trace equivalence and is strictly finer, separating genuine concurrency from interleaved choice, which a trace comparison cannot, and signature inclusion implies trace inclusion. In a recovery study on one object-centric log, the discovered causal net has exactly the ground-truth signature, while the discovered Petri net's signature strictly contains it and locates every behaviour the Petri net adds in its silent structure. The gain is largest for object-centric data, where a single log supports several notations at once. The four notations become one calculus, in which a translation between them is a claim that can be checked.

0.35

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

cs.PL ·2026-11-18 ·Xueying Qin, Marco Peressotti, Fabrizio Montesi
theory similarity 0.60
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

Universal Properties of Petri Net Unfoldings

cs.LO math.CT ·2026-09-15 ·Serge Lechenne, Hugo Paquet
published similarity 0.59
Abstract

It is an established idea in concurrency theory that every Petri net admits an unfolding semantics. This is a denotational object that represents its domain of possible executions. Unfoldings play an important role in practical analysis and verification. This paper is concerned with the following well-known problem: while the unfolding resembles a universal construction in the category of Petri nets, it generally fails to satisfy the expected universal property. This is because the unfolding construction overlooks the net's internal symmetries. There are two solutions: make these symmetries explicit to obtain a weak universal property (one that holds only ''up to symmetry''); or break the symmetries by assigning individual identities to components of the net. We review these two solutions and establish, in each case, a universal unfolding of Petri nets to event structures. This paper demonstrates a 2-categorical approach to Petri net unfoldings. We show that each unfolding semantics determines a 2-categorical relative adjunction involving Petri nets and event structures. Viewed in this way, the above two constructions can be related formally via an appropriate morphism of adjunctions. We exhibit a 2-density property of event structures which implies that unfolding functors are essentially unique.

0.40

Full Provenance on the COSS Causal Axis: An Event-Level Closure of Causal Attribution and Confused-Deputy Exclusion

cs.CR cs.DC ·2026-11-04 ·Nicola Gallo
publishedtheory similarity 0.59
Abstract · 19 pages

Provenance Identity Continuity (PIC) represents an authority-use event as an operation/resource behavior situated in a causal lineage, $(o,r,\ell)\in O\times R\times L$. We make the causal occurrence itself primitive: a represented security-relevant causal graph $(E,\to_c)$ in which each occurrence has a unique causal history, so the consistent event-lineage space is canonically isomorphic to $E$. The modeled execution has one causal partial order; distinct lineages are distinct causal histories inside it and may share a root while diverging into incomparable branches. PIC's $O\times R\times L$ is the authority-behavior projection of this space, and Causally Ordered Security-State (COSS) continuity generalizes it to an arbitrary behavior product over the same causal execution. On this semantics we prove an architecture-independent confused-deputy exclusion theorem. PIC continuation requires $C(e')\subseteq C(e)$ on every ordinary causal edge, so descendants are bounded by their ancestors; at an ordinary join, authority available on only one incoming branch cannot be resurrected, even when branches share a common root. Non-conservative combination must be an explicit authorized composition or relaxation event. With protected-effect mediation, an effect caused by request $q$ through an ordinary authority segment can exercise only authority in $C(q)$, so a confused-deputy state is contradictory. The result holds for any system whose protected request-to-effect causes are faithfully represented and whose ordinary authority transport satisfies PIC. We revisit Rajani, Garg, and Rezk: their value, control-flow, and initial-heap attacks are different witnesses of causal ancestry, so full provenance is an evidence mechanism for recovering edges of the causal graph, not the foundation of the PIC theorem. Finally we lift it to the COSS product of heterogeneous security-state coordinates.

0.44

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

CONCURDEP: Event-Guided Analysis of Dependency Invalidation in CPython Concurrency

cs.CR cs.SE ·2026-09-23 ·Baihong Chen, Hadley Westover, Wen Li
similarity 0.58
Abstract

Removing CPython's Global Interpreter Lock (GIL) exposes native code to concurrency absent from ordinary C types. Mutation or re-entry can revoke a borrowed object, storage pointer, traversal state, or lease between acquisition and use while its owner remains alive, causing native memory errors and runtime-state corruption. Race analyses track conflicting accesses. Python/C lifecycle analyses track individual object states. These reporting units leave implicit owner-subject-storage relations disconnected from later uses under parallel and re-entrant events. We present CONCURDEP, a source-level static analysis of dependency invalidation. Its key insight is to represent the runtime property a native use requires and ask which target-matched event can revoke it within the dependency's live region. CONCURDEP recovers runtime-semantic dependencies, connects them to events through an event-aware native concurrency dependency graph, and applies property-specific state and protection transfers through a shared engine and six mechanism plugins. CONCURDEP correctly classifies all 180 matched semantic-conformance cases and analyzes each of three production CPython releases with five-run medians of 22.13-27.66 seconds and 670-784 MiB peak resident memory. Source auditing confirms 1,094 of 4,273 unique production fingerprints (25.60% confirmation yield). Removing derived relation recovery loses 25-44 represented roots per release; removing cross-entry events loses 73-94. The study identifies 144 distinct bugs across free-threaded and conventional-GIL builds, including 95 previously unreported in public sources. These results show that explicit dependency, event, and property semantics expose consequential runtime failures across API boundaries and execution modes at release scale.

0.21