A Principled Approach to Concurrency, Nondeterminism, and Asynchrony in Choreographies
Xueying Qin, Marco Peressotti, Fabrizio Montesi
cs.PL
Nov 18, 2026 · v1
TL;DR
The entire choreographic calculus Nyarlathotep, including EPP soundness, completeness, communication safety and deadlock freedom, is mechanised in about 20,000 lines of Lean 4 using CSLib.
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.
Problem
Choreographic programming compiles global programs into communicating endpoint programs via endpoint projection (EPP). No existing choreographic programming framework combines asynchronous communication with choreographic nondeterminism, and both features are notoriously hard to model correctly.
Approach
Nyarlathotep extends the Lean-mechanised calculus Mech with asynchronous labelled-transition semantics for choreographies and networks. It adds only two runtime terms and supports general branching, out-of-order execution, and parameterised recursive procedures. A localised process semantics enables compositional proofs of EPP correctness. Everything is mechanised in Lean 4, reusing CSLib's FinFun and its multi-step transition relation.
Results
EPP is proved sound and complete, giving strong behavioural equivalence between choreographies and projected networks. Projected networks are proved communication-safe and deadlock-free. The Lean 4 mechanisation is about 20k lines, compared with about 40k for Mech, which supports fewer features.