CS Paper Radar

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

Xueying Qin, Marco Peressotti, Fabrizio Montesi

cs.PL ·submitted 2026-11-18 15:52 UTC · v1
theory

Abstract

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.

Comment
31 pages including appendix

Closest papers

Nearest neighbours by meaning across the whole index.

What is a Good Projection?: Correctness and Separation Results of End-Point Projections

cs.PL cs.LO ·2026-10-20 ·Jake Masters, Nobuko Yoshida
top venuetheory similarity 0.75
Abstract · 91 pages. 6 figures. Conditionally accepted to POPL 2027

\emph{Multiparty session types} (MPST) is a type discipline for ensuring distributed programs are implemented correctly \emph{by construction}. MPST starts by specifying a choreographic protocol as a \emph{global type} and \emph{projects} it onto each participant, generating \emph{local types} with a guarantee of type soundness and deadlock-freedom. A central issue of MPST is that its type soundness is fragile, as it must be proven each time with respect to a chosen projection algorithm under specific semantics with a specific program correctness goal. To overcome this problem, we propose general criteria for a \emph{good projection} -- a set of requirements for projection algorithms by which type soundness, deadlock-freedom and liveness of distributed programs are \emph{automatically} derived. Using the criteria, we prove that 8 distinct projections in the literature are good under both synchronous and asynchronous semantics, and that 4 are incorrect, failing type soundness. We extend the good projection criteria to mixed choice global types and asynchronous communication optimisations, proposing new ``good projection'' algorithms. We apply properties of good projections to prove \emph{separation} and \emph{expressiveness} results over the projection algorithms and MPST typing systems. Having a generalised typing system that is robust with respect to the good projection criteria, we provide an implementation with mixed choice global types that is \emph{modular} with respect to a chosen projection algorithm and desired program properties. Our separation results help programmers make informed trade-offs between complexity and expressiveness when choosing projection algorithms, and our theory ensures their chosen algorithms are correctly applied.

0.45

Mechanizing Choreographic Programs and Hoare Logic with State Transformers

cs.PL ·2026-08-17 ·Timon Böhler, Simon Daniel, David Richter, Pascal Weisenburger, Mira Mezini
theory similarity 0.70
Abstract · To be published in the TyDe 2026 proceedings

Choreographic programming is a programming model for developing distributed applications where an entire communication protocol is written as a single program, which a compiler then projects to one process per participant. Choreographic programming abstracts over low-level network communication primitives such as sockets, and provides a high degree of safety guarantees with deadlock freedom ensured by construction. Mechanizing choreographies necessarily deals with both operations specific to distributed programming and standard (local) operations that also occur in non-distributed programs, as well as the typical issues of binding and substitution. We aim to sidestep the latter issues, thereby obtaining a more concise mechanization that focuses on the essential distributed aspects of choreographies. To this end, we use a method recently proposed by Thiemann to elegantly model deadlock-free processes in a dependently typed language: Using state transformers to represent the computations performed by each process. We bring the state transformer model to choreographies, allowing us to reduce the usual mechanization effort around binding and substitution, and to abstract over the details of the "local" aspects of the language. We mechanize in Lean a choreographic language that supports point-to-point communication, broadcasting, recursive procedures, and local stateful methods, allowing each participant to be assigned a different set of methods. We prove soundness and completeness of endpoint projection, establish deadlock freedom for the projected processes, prove confluence, and verify a Hoare logic for choreographies.

0.33

On Eliminating the Impossible with Dependent Types: Choreographic Libraries with Proof-Carrying Located Values

cs.PL ·2026-08-20 ·Simon Daniel, Timon Böhler, David Richter, Pascal Weisenburger, Mira Mezini
similarity 0.67
Abstract

With growing complexity, distributed software systems become increasingly challenging to maintain and reason about. When implementing a distributed protocol, developers must ensure manually that the different components fit together. Choreographic programming addresses this challenge by specifying global protocols in a single program and projecting them into communicating processes, so-called endpoints. Recent choreographic approaches are designed as programming libraries that embed this paradigm into a host language like Haskell or Rust. In these designs, we observe common cases of partiality: unreachable branches in endpoint projection (EPP) and located-value access can trigger runtime errors or undefined behavior, relying on manual discipline of library maintainers rather than being statically type-checked. Also, some programs require users to write down dummy branches that should not be reachable, for example when branching on sum types. To close this gap, we use the dependently typed Lean programming language to implement a similar choreographic library. We show how we are able to move from a partial EPP to a total EPP function, and also eliminate cases of partiality in user-written code with pattern matching on sum types. ChorLean ensures total EPP and safe value access via proof-carrying located values, passing Lean's totality checker without undefined cases, while supporting the same feature set as libraries like MultiChor.

0.25

Coexponential Exploration in the Clef Programming Language

cs.PL cs.DCcs.LO ·2026-10-09 ·Houston Haynes
theory similarity 0.66
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

Transition Systems from Causal Reversible Bundle Event Structures

cs.GT ·2026-08-25 ·Nataliya Gribovskaya, Irina Virbitskaite
published similarity 0.65
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 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.63
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

Decreasing Diagrams are Complete for Confluence

cs.LO ·2026-10-05 ·Jörg Endrullis, Ievgen Ivanov, Femke van Raamsdonk
theory similarity 0.62
Abstract

Confluence is a fundamental property of nondeterministic computations, arising from parallelism, concurrency, or freedom in the evaluation order. It guarantees that such a computation always yields the same result, regardless of the order in which steps are taken. The decreasing diagrams technique of van Oostrom is one of the most versatile methods for establishing confluence of transition systems (abstract rewriting systems). It reduces global confluence to local confluence: a system is confluent whenever its transitions admit a locally decreasing labeling. Essentially all classical confluence criteria arise as corollaries. A central question, posed by van Oostrom in 1993, asks whether the decreasing diagrams technique is complete: Does every confluent transition system admit a locally decreasing labeling? This is Problem 56 of the RTA List of Open Problems. A positive answer was known only for countable systems, and recently up to the first uncountable cardinal $\aleph_1$. The general case remained open. We settle this thirty-three-year-old problem in full. We prove that every confluent transition system admits a locally decreasing labeling using only three labels. This bound is optimal, as two labels do not suffice even at the first uncountable cardinality. It follows that this single criterion can, in principle, certify the confluence of every confluent system, and hence of every confluent program. The entire development is machine-checked in the Isabelle/HOL and Lean proof assistants and relies only on classical logic and the axiom of choice.

0.23

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