betaFeedback

WorksComputer Science

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

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.

Introduction

Traditionally, concurrent and distributed systems are programmed from a local perspective. Developers write programs for individual endpoints, and the overall behaviour of the system emerges from interactions amongst those endpoints. With such an approach, concurrent and distributed systems are prone to critical errors including deadlocks and mismatched communications, and the overall system behaviours are hard to reason about.

Choreographic programming (CP) is an emerging correct-by-construction programming paradigm, which addresses these issues by enabling developers to program concurrent and distributed systems from a global perspective [20, 22]. A choreography is a global program that specifies the intended computation and the interactions among endpoints, which are processes. Endpoint projection (EPP) automatically compiles a choreography into a network of endpoint programs that follow the behaviours specified by the choreography. The correctness of EPP establishes behavioural equivalence between choreographies and their projected programs. Consequently, the safety and liveness properties characterised by a choreography are preserved in networks. In practice, there are many stand-alone and library-level implementations of CP, such as Choral [Giallorenzo et al. 2024], Klor [18], Chorex [Wieser and Greenman 2025], HasChor [30], MultiChor [3], and UniChorn [9].

Theories of CP have been rapidly developed over the past few years, and some have been accompanied by substantial mechanisation efforts, opening up opportunities to build certified compiler frameworks for programming concurrent and distributed systems. However, an asynchronous CP framework with choreographic nondeterminism is still missing.

Asynchrony and nondeterminism are each difficult to model. The textbook semantics for nondeterministic choreographic choice is wrong [21, 27]. In the multiparty session types (MPST) community, researchers have found flaws in subject-reduction proofs [8, 29, 32] and shown that a previously proposed asynchronous subtyping relation is undecidable [5]. Work on mixed choice highlights the difficulty of coordinating participants in the presence of nondeterminism, under both synchronous and asynchronous communication [4, 24].

However, an asynchronous nondeterministic CP framework is necessary for expressing complex system behaviours. In example 1.1, we use a recursive choreographic procedure definition to model a reusable lock. With asynchrony and nondeterminism, two processes p1p_1 and p2p_2 repeatedly compete to update a shared inventory at ss, which manages the lock. ss replies with ok to the first request it receives, regardless of the order in which the requests were sent. After sending ok, ss can take a local snapshot of the inventory while the reply is still queued for the winner. The winner works with ss in the procedure WW, where ss can use the snapshot to restore the inventory if an update fails. The completion of WW serves as an implicit release. The notation C1+sC2C_1 +_s C_2 denotes a nondeterministic choreographic choice between C1C_1 and C2C_2, which ss resolves by taking a step in one of the branches.

Example 1.1 (A Deadlock-Free Reusable Lock).

X(s,p1,p2)=(p1→s[req];s→p1[ok];s.backup:=snapshot(inventory);W(p1,s);p2→s[req];s→p2[ko]+sp2→s[req];s→p2[ok];s.backup:=snapshot(inventory);W(p2,s);p1→s[req];s→p1[ko]);X(s,p1,p2)\begin{aligned} X(s,p_1,p_2) ={}& (p_1 \to s[\mathrm{req}] \mathbin{;} s \to p_1[\mathrm{ok}] \mathbin{;} s.\mathit{backup} := \mathit{snapshot}(\mathit{inventory}) \mathbin{;} \\ & W(p_1,s) \mathbin{;} p_2 \to s[\mathrm{req}] \mathbin{;} s \to p_2[\mathrm{ko}] \\ & +_s p_2 \to s[\mathrm{req}] \mathbin{;} s \to p_2[\mathrm{ok}] \mathbin{;} s.\mathit{backup} := \mathit{snapshot}(\mathit{inventory}) \mathbin{;} \\ & W(p_2,s) \mathbin{;} p_1 \to s[\mathrm{req}] \mathbin{;} s \to p_1[\mathrm{ko}]) \mathbin{;} X(s,p_1,p_2) \end{aligned}

Endpoint projection produces process procedure definitions for the reusable lock, shown in example 1.2, each specifying the local behaviour of one of the participating processes. Each process can enter its procedure call independently. Repeatedly, p1p_1 and p2p_2 send req to ss (s⊕reqs \oplus\mathrm{req}), each participating in WW only upon receiving ok. Branches labelled by ok and ko are merged into a branching term that waits to receive a selection label from ss. The first request that ss receives resolves the nondeterministic choice (+). If both requests are queued, either can win. After sending ok, ss can take a local snapshot of the inventory while the reply is still queued. It then executes its part of WW before receiving and rejecting the other request with ko and repeating the procedure. The (♯) notation here is the sequential composition of process terms, formally defined in § 4.2.1.

Example 1.2 (A Reusable Lock as Process Procedure Definitions). The two process procedure definitions for clients p1p_1 and p2p_2 are:

X2(s,p2)=s⊕req;s&{ok:W1(s), ko:0};(X2(s,p2)),X_2(s,p_2) = s \oplus\mathrm{req} \mathbin{;} s \& \{\mathrm{ok}: W_1(s),\ \mathrm{ko}: 0\} \mathbin{;} (X_2(s,p_2)),

and

X3(s,p1)=s⊕req;s&{ko:0, ok:W1(s)};(X3(s,p1)).X_3(s,p_1) = s \oplus\mathrm{req} \mathbin{;} s \& \{\mathrm{ko}: 0,\ \mathrm{ok}: W_1(s)\} \mathbin{;} (X_3(s,p_1)).

The definition for the server is:

X1(p1,p2)=(p1&{req:p1⊕ok;backup:=snapshot(inventory);W2(p1);p2&{req:p2⊕ko}}+p2&{req:p2⊕ok;backup:=snapshot(inventory);W2(p2);p1&{req:p1⊕ko}});X1(p1,p2)\begin{aligned} X_1(p_1,p_2) ={}& (p_1 \& \{\mathrm{req}: p_1 \oplus\mathrm{ok} \mathbin{;} \mathit{backup} := \mathit{snapshot}(\mathit{inventory}) \mathbin{;} \\ & W_2(p_1) \mathbin{;} p_2 \& \{\mathrm{req}: p_2 \oplus\mathrm{ko}\}\} \\ & + p_2 \& \{\mathrm{req}: p_2 \oplus\mathrm{ok} \mathbin{;} \mathit{backup} := \mathit{snapshot}(\mathit{inventory}) \mathbin{;} \\ & W_2(p_2) \mathbin{;} p_1 \& \{\mathrm{req}: p_1 \oplus\mathrm{ko}\}\}) \mathbin{;} X_1(p_1,p_2) \end{aligned}

We have studied existing theories of CP that could serve as a starting point to developing a theory expressive enough to express examples like example 1.1. We see two possible expressive and machine-checked candidates, with different approaches to concurrency. The state-of-the-art functional choreographic language λQC\lambda_{\mathrm{QC}} [28] extends Pirouette [15], supporting features such as process polymorphism and higher-order functions. However, it only supports synchronous communication. On top of that, invoking a function application requires all processes to synchronise, even those uninvolved in the call. This design not only conflicts with the concurrent semantics of distributed systems but also poses substantial obstacles to adding choreographic nondeterminism. Introducing +s+_s under λQC\lambda_{\mathrm{QC}}'s global application rule leaves the example lock unprojectable: p1p_1 and p2p_2 cannot enter the procedure calls independently, a step the losing process to joining the procedure need to be added, which causes two branches unmergeable. Following the textbook approach [22], Mech [27] does not require global synchronisation and correctly models the semantics of nondeterministic choreographic choice. But its synchronous communication produces cumbersome nondeterministic semantics and limits the behaviours it can express (cf. § 5). Mech’s approach to concurrency and algebraic characterisations for choreographies still make it a good starting point for extending CP.

In this paper we present Nyarlathotep, a semantic foundation for asynchronous and nondeterministic choreographies, which also features out-of-order execution, general branching, and general recursion parameterised over processes that allows processes to enter calls independently. Our paper makes the following contributions:

  • We present the first formalism for asynchronous and nondeterministic choreographies. We design new operational semantics for choreographies and networks to capture the interplay amongst asynchrony, nondeterminism, and out-of-order execution.

  • Nyarlathotep’s operational semantics has a new locality property: unlike in Mech, where synchronous transitions can involve multiple processes, in Nyarlathotep each transition concerns only one active process, both in choreographies and networks. This property enables more structured and compositional reasoning about the correctness of EPP.

  • We prove the correctness of EPP, which yields networks behaviourally equivalent to their source choreographies and guarantees communication safety and deadlock freedom.

  • We mechanise all results in Lean 4, providing a machine-checked formal framework that enables the future development of a certified compiler for CP. Benefitting from the locality property, the size of the mechanisation of Nyarlathotep is only around half of Mech’s.

Background

The design of Nyarlathotep builds on Mech’s account of concurrency in CP. We briefly introduce core reusable features of Mech and give a high-level overview of CP.

Mech

Mech is a first-order choreographic calculus mechanised in Lean 4. It models synchronous communication and supports multi-way branching, general recursion with process parameters and independent procedure entry, and nondeterministic choreographic choice. Mech abstracts over local computations by taking an evaluation relation for local expressions as a parameter. This allows the choreographic semantics to describe how processes interact independently of how they compute their local results. We use Mech’s invoicing choreography example example 2.1 to give an overview of the design of a choreographic programming language.

Example 2.1 (An Invoicing Choreography). The shop p decides whether to request payment, issue a reimbursement, or skip invoicing. The guards are evaluated at p. Since the customer q has a different role in each branch, p sends it a selection label before proceeding.

Cinv≔if p.pay() then p→q[PAY];p.invoice()→q.x;0C_{\mathrm{inv}} \coloneqq\text{if } p.\mathrm{pay}() \text{ then } p \to q[\mathrm{PAY}] \mathbin{;} p.\mathrm{invoice}() \to q.x \mathbin{;} 0
else if p.reimburse() then p→q[REIMBURSE];q.coords()→p.c;p.invoice(c)→q.x;0\text{else if } p.\mathrm{reimburse}() \text{ then } p \to q[\mathrm{REIMBURSE}] \mathbin{;} q.\mathrm{coords}() \to p.c \mathbin{;} p.\mathrm{invoice}(c) \to q.x \mathbin{;} 0
else p→q[SKIP];0\text{else } p \to q[\mathrm{SKIP}] \mathbin{;} 0

Mech defines operational semantics for both choreographies and endpoint networks. At the choreographic level, actions on disjoint processes can execute out of order. An assignment at a third process, for instance, can proceed independently of the exchange of bank details. The exchange itself is synchronous. The send at q and the matching receive at p occur in a single transition. EPP produces the network in example example 2.2, where each endpoint runs the following program.

Example 2.2 (EPP of the Invoicing Choreography). The shop p, as a guard process, retains the two evaluations of guard expressions. The customer q’s three possible behaviours are merged into one branching term that waits for a label from the shop. We describe this merge operation in section 2.2.

⟦Cinv⟧=p[ if pay() thenq⊕PAY ; q!invoice() ; 0else if reimburse() thenq⊕REIMBURSE ; q?c ; q!invoice(c) ; 0else q⊕SKIP ; 0]q[p & {PAY:p?x ; 0,REIMBURSE:p!coords() ; p?x ; 0,SKIP:0}]\llbracket C_{\mathrm{inv}} \rrbracket= \begin{array}{l} p[\ \mathbf{if}\ pay() \ \mathbf{then}\\ \qquad q \oplus\mathrm{PAY}\ ;\ q!invoice()\ ;\ 0\\ \mathbf{else\ if}\ reimburse() \ \mathbf{then}\\ \qquad q \oplus\mathrm{REIMBURSE}\ ;\ q?c\ ;\ q!invoice(c)\ ;\ 0\\ \mathbf{else}\ q \oplus\mathrm{SKIP}\ ;\ 0] \end{array} \quad \begin{array}{l} q[p\ \&\ \{\mathrm{PAY}:p?x\ ;\ 0,\\ \qquad\mathrm{REIMBURSE}:p!coords()\ ;\ p?x\ ;\ 0,\\ \qquad\mathrm{SKIP}:0\}] \end{array}

Select and Merge: the Algebraic Approach to Handling Knowledge of Choice (KoC)

The select-and-merge approach handles knowledge of choice (KoC) in choreographic programming [20, 22]. As shown in example 2.2, a selection communicates the outcome of a choice as a label, and merge combines the projected alternatives into a single endpoint program.

We adopt Mech’s formulation of the selection and full merge [13] approach. EPP preserves a conditional at the process that evaluates its guard and projects a choreographic choice to a nondeterministic choice at the choice-resolving process. At every other process, EPP projects the alternatives separately and combines them using the merge operation (⊔\sqcup).

Mech defines merge on optional process terms (Process?) and optional instructions (PInstr?) by mutual recursion. We formally introduce the process language in section 4.1. A successful merge of process terms returns (PP) for the combined term PP. Incompatible terms and failed inputs yield (⟨⟩\langle\rangle). Two branching terms can merge when they expect a label from the same sender. The result offers the union of their labels. A label offered by only one term keeps its continuation, while a label offered by both requires their continuations to merge recursively.

Merge is associative, commutative, and idempotent, making (Process?, ⊔\sqcup) a join-semilattice. It introduces a partial order, which is the more branches relation: P~⊒Q~\tilde{P} \sqsupseteq\tilde{Q} if and only if P~⊔Q~=P~\tilde{P} \sqcup\tilde{Q} = \tilde{P}. Note that P~\tilde{P} denotes a process term that can either be (PP) or (⟨⟩\langle\rangle). ⊒\sqsupseteq is a simulation relation, meaning that PP offers every label that QQ offers at the corresponding branching terms and may offer additional labels. The order enables us to compare a residual network that still offers several alternatives with the projection of a choreography that has already resolved a choice. For the formal definitions of merge and the more branches relation, and for their properties, see appendix § 16.

Formal Preliminaries

We introduce formal preliminaries we adopt from Mech in the development of Nyarlathotep.

Parameters. To design a local language agnostic CP framework, our models do not fix internal details of local computations at processes. Specifically, we require the following parameters:

  • A set of process names (PName) used to identify processes, ranged over by pp.

  • A set of values (Val) that processes can compute, ranged over by vv.

  • A set of variables (Var) that processes use to store values, ranged over by xx.

  • A set of function names (F) used to identify local functions that processes can invoke.

  • A set of selection labels (SLabel) used by processes to offer alternative behaviours.

  • A set of procedure names (ProcName) used to identify recursive procedures in programs.

Function Support. Given a function ff whose codomain has a zero element, we write supp(ff) for its support, defined by: supp⁡(f)≜{a∈A∣f(a)≠0}\operatorname{supp}(f) \triangleq\{a \in A \mid f(a) \ne0\}.

Expressions, Stores, and Evaluation of Expressions. The local language expressions are of the form:

Expression (Expr)e::=v∣x∣f(e⃗)\mathrm{Expression}\ (\mathbf{Expr})\qquad e ::= v \mid x \mid f(\vec{e})
C::={Xi(p⃗i)=Ci}i∈IC::=I;C∣0I::=p.x:=e∣p.e→q.x∣p→q[l]∣p⇝q.x∣p⇝q[l]∣if p.e then C1 else C2∣C1+pC2∣X(p⃗)∣q:X(p⃗).C\begin{aligned} \mathcal{C} &::= \{X_i(\vec{p}_i)=C_i\}_{i\in I}\\ C &::= I;C \mid0\\ I &::= p.x := e \mid p.e \to q.x \mid p \to q[l]\\ &\mid p \leadsto q.x \mid p \leadsto q[l] \mid\text{if }p.e\text{ then }C_1\text{ else }C_2\\ &\mid C_1 +_p C_2 \mid X(\vec{p}) \mid q:X(\vec{p}).C \end{aligned}

fig:1. Syntax of Choreographies in Nyarlathotep

A global store Σ\Sigma is a function mapping process names to local stores, representing the memory state of the system. A local store σ\sigma is a function mapping variables to values, representing the local memory of a process. We define them as follows:

Global Store (GStore) Σ:PName→LStore\Sigma: \mathrm{PName} \to\mathrm{LStore}

Local Store (LStore) σ:Var→Val\sigma: \mathrm{Var} \to\mathrm{Val}

We write σ[x↦v]\sigma[x \mapsto v] for the update of xx to vv in a local store, and Σ[p.x↦v]\Sigma[p.x \mapsto v] for the corresponding update in the local store of pp (cf. definition B.1). The evaluation relation σ⊢e↓v\sigma\vdash e \downarrow v states that ee evaluates to vv under σ\sigma. We assume only that ↓\downarrow is total; evaluation can be nondeterministic.

Choreographies

We introduce the formal syntax and semantics of choreographies in Nyarlathotep. Throughout the paper, we shade the components in our formalism that model asynchrony and choreographic nondeterminism. While designing new semantics for both choreographies and networks, we add only two runtime terms and retain the surface syntax of Mech. This makes Nyarlathotep an ergonomic extension of Mech modelling richer behaviours with the same program encodings.

Syntax

fig:1 shows the formal syntax of choreographies in Nyarlathotep, where we mutually define choreographies (CC) and their instructions (II). A choreography is either a sequence of instructions, or a terminated choreography 00. For readability, we often omit trailing 00s in examples. The two new runtime instructions p⇝q.xp \leadsto q.x and p⇝q[l]p \leadsto q[l] represent a pending receive at qq after pp sends a value or a selection label, respectively. We define standard functions pn⁡(C)\operatorname{pn}(C) and pn⁡(I)\operatorname{pn}(I) for gathering the (active) process names in choreographies and instructions. Figure 3 shows selected definitions. These functions are particularly important for modelling out-of-order execution in the semantics.

Selected definitions of pn

Figure 3. Selected Definitions of pn (Full definitions are in definitions A.1 and A.2)

Semantics

We define the operational semantics of choreographies as a labelled transition system (LTS) whose states are configurations of the form ⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle, where CC is a choreography, Σ\Sigma is a global store mapping process names to their local stores, KK is a messaging state, and C\mathcal{C} is a set of choreographic procedure definitions. A transition takes the form of ⟨C,Σ,K,C⟩→μ⟨C′,Σ′,K′,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\mu} \langle C',\Sigma',K',\mathcal{C}\rangle, where μ\mu is a transition label. We first introduce some important notations and definitions used in our semantics.

Transition Labels

A transition label μ\mu for the LTS in Mech is defined as a pair (ρ,ζ)(\rho,\zeta), where ρ\rho is a pre-transition label indicating the action performed and ζ\zeta maps process names to lists of choice labels, left or right, indicating the chosen branches for a choice-resolving process and carrying the communication synchronisation obligation in choreographic nondeterminism.

Since Nyarlathotep models asynchronous communications, transition labels no longer need to carry the synchronisation obligation, yielding a straightforward design which takes a list structure.

μ::=assign⁡@p∣p.v→q!∣p.v→q?∣p→q[l!]∣p→q[l?]∣then⁡@p∣else⁡@p∣call⁡@p∣skip⁡@p∣left⁡@p::μ∣right⁡@p::μ\begin{aligned} \mu::={}& \operatorname{assign}@p \mid p.v \to q! \mid p.v \to q? \mid p \to q[l!] \mid p \to q[l?]\\ &\mid\operatorname{then}@p \mid\operatorname{else}@p \mid\operatorname{call}@p \mid\operatorname{skip}@p \mid\operatorname{left}@p::\mu\mid\operatorname{right}@p::\mu \end{aligned}

fig:2. Transition Labels in Nyarlathotep

There are two major changes to model the asynchronous semantics. First, sending and receiving actions are treated as two separate steps, reflected in p.v→q!p.v \to q!, p.v→q?p.v \to q?, p→q[l]!p \to q[l]!, and p→q[l]?p \to q[l]?. Second, transition labels for modelling nondeterministic behaviours now become cleaner: it states the choice-resolving behaviour without carrying the synchronisation obligations. We discuss the interaction between asynchrony/synchrony and nondeterminism in § 5. We also define the function pn⁡\operatorname{pn} for gathering active process names in a transition label, shown in Figure 3.

Monoidal Construction of Sequential Composition

In Figure 4, we define a semantic operator, the sequential composition operator \mathbin{\fatsemi}, for handling the continuation of choreographies in transitions. The set of choreographies together with the sequential composition operator \mathbin{\fatsemi} forms a monoid, where 00 is the identity element and \mathbin{\fatsemi} is the associative operator (see proposition F.1).

Sequential composition of choreographies

Figure 4. Sequential Composition of Choreographies

Messaging State

The messaging state KK in Nyarlathotep records messages that have been sent and are awaiting receipt. A message mm is either a value vv or a selection label ll, and [M][M] denotes lists of messages.

Message (M) m::=v∣lm ::= v \mid l    Messaging State K:PName→PName→[M]K : \mathrm{PName} \to\mathrm{PName} \to[M]

For each sender pp and receiver qq, K(q,p)K(q,p) is a first-in, first-out (FIFO) queue of messages from pp to qq. We write K[(q,p)↦m⃗]K[(q,p) \mapsto\vec{m}] for the update that sets the queue from pp to qq to m⃗\vec{m}.

LTS for Choreographies

Figure 5 gives the rules for the asynchronous communications and choreographic choice. A value communication p.e→q.xp.e \to q.x takes two transitions. In SEND-VAL, pp evaluates ee in its local store. The resulting value vv is then appended to the message queue for the communication from pp to qq in the messaging state KK, namely K(q,p)K(q,p), and the transition takes the communication to a state with a pending receive p∼q.xp \mathrel{\sim} q.x. In RECV-VAL, qq consumes the value at the head of that queue, stores it in its local variable xx, and continues with CC. Communications over selection labels use the same mechanism, as shown in SEND-SEL and RECV-SEL.

For modelling choreographic nondeterminism, rules CHOICE-L and CHOICE-R resolve a choreographic choice by taking a transition in one of its branches. For instance, if C1C_1 takes a μ\mu-transition to C1′C'_1 and p∈pn⁡(μ)p \in\operatorname{pn}(\mu), then CHOICE-L records the decision in left⁡@p::μ\operatorname{left}@p :: \mu and continues with C'_1 \mathbin{\fatsemi} C. For a communication from pp to qq, the send label has process set {p}\{p\} and the receive label has process set {q}\{q\}. A choice at qq can therefore be resolved by receiving the message.

Figure 6 gives the remaining rules. An assignment updates the local store, and a conditional evaluates its guard expression at the guard process to choose a branch. In example 2.1, for example, the shop pp evaluates pay()pay() to decide whether to take the payment branch. Rules CALL-FIRST and CALL-ENTER model general recursion. Rule CALL-FIRST unfolds the procedure body with the actual

process arguments and records the other participants as pending. Here, We write C[p⃗/q⃗]C[\vec{p}/\vec{q}] for simultaneous substitution of process names in a choreography (cf. definitions B.2 and B.3). Each of those participants enters by removing its own marker via CALL-ENTER. The garbage collection rules SKIP-L and SKIP-R are important for ensuring deadlock freedom. They permit either branch when the choice-resolving process is absent from both branches.

We have three rules for modelling out-of-order executions. Rule DELAY allows the continuation CC to perform a μ\mu-transition when the active processes in μ\mu are not mentioned in pn⁡(I)\operatorname{pn}(I). For instance, in example 1.1, after ss sends OK to p1p_1, DELAY allows ss to take the snapshot while the reply is queued. Rules DELAY-COND and DELAY-CHOICE allow both branches to take a transition with the same label μ\mu. The guard process or choice-resolving process must be absent from pn⁡(μ)\operatorname{pn}(\mu), so the conditional or choice remains pending. Using the rules DELAY and DELAY-CHOICE, together with CHOICE-L and CHOICE-R, we can express interesting transitions for the lock acquisition in example 1.1.

Consider one unfolded iteration in which p1p_1 sends its request before p2p_2, but p2p_2’s request is received by ss first, leading to p2p_2 winning the competition. Let C1C_1 be the left branch and C2C_2 the right branch. Both request queues are initially empty in K0K_0. By DELAY, each send can pass instructions involving only the other client and ss. Each send thus produces the same label and queue update in both branches. Since ss is absent from the process set of either send label, DELAY-CHOICE advances both branches and leaves the choice unresolved. The two sends update separate queues. The sends and the subsequent receive produce the following messaging states: K1=K0[(s,p1)↦[REQ]]K_1 = K_0[(s,p_1) \mapsto[\mathrm{REQ}]], K2=K1[(s,p2)↦[REQ]]K_2 = K_1[(s,p_2) \mapsto[\mathrm{REQ}]], K3=K2[(s,p2)↦[]]=K1K_3 = K_2[(s,p_2) \mapsto[]] = K_1.

The corresponding choreographic transitions for this round of competition are shown below:

Semantics of Choreographies in Nyarlathotep, Rules Concerning Asynchrony and Nondeterminism

Figure 5. Semantics of Choreographies in Nyarlathotep, Rules Concerning Asynchrony and Nondeterminism

Semantics of Choreographies in Nyarlathotep, Remaining Rules

Figure 6. Semantics of Choreographies in Nyarlathotep, Remaining Rules

The first send yields C1′C'_1 and C2′C'_2, and the second yields C1′′C''_1 and C2′′C''_2. When s receives p2_2’s request, CHOICE-R selects the right branch. The request from p1_1 remains queued, with its pending receive following W(p2,s)W(\mathrm{p}_2,\mathrm{s}) in C2winC_{2\mathrm{win}}. The definitions below show the resulting choreographies in each transition:

C1′≜p1⇝s[REQ];s→p1[OK];s.backup:=snapshot(inventory);W(p1,s);p2→s[REQ];s→p2[KO],C2′≜p2→s[REQ];s→p2[OK];s.backup:=snapshot(inventory);W(p2,s);p1⇝s[REQ];s→p1[KO],C1′′≜p1⇝s[REQ];s→p1[OK];s.backup:=snapshot(inventory);W(p1,s);p2⇝s[REQ];s→p2[KO],C2′′≜p2⇝s[REQ];s→p2[OK];s.backup:=snapshot(inventory);W(p2,s);p1⇝s[REQ];s→p1[KO],C2win≜s→p2[OK];s.backup:=snapshot(inventory);W(p2,s);p1⇝s[REQ];s→p1[KO].\begin{aligned} C'_1 &\triangleq p_1\leadsto s[\mathrm{REQ}];s\to p_1[\mathrm{OK}];s.\mathit{backup}:=\mathit{snapshot}(\mathit{inventory});W(p_1,s);p_2\to s[\mathrm{REQ}];s\to p_2[\mathrm{KO}],\\ C'_2 &\triangleq p_2\to s[\mathrm{REQ}];s\to p_2[\mathrm{OK}];s.\mathit{backup}:=\mathit{snapshot}(\mathit{inventory});W(p_2,s);p_1\leadsto s[\mathrm{REQ}];s\to p_1[\mathrm{KO}],\\ C''_1 &\triangleq p_1\leadsto s[\mathrm{REQ}];s\to p_1[\mathrm{OK}];s.\mathit{backup}:=\mathit{snapshot}(\mathit{inventory});W(p_1,s);p_2\leadsto s[\mathrm{REQ}];s\to p_2[\mathrm{KO}],\\ C''_2 &\triangleq p_2\leadsto s[\mathrm{REQ}];s\to p_2[\mathrm{OK}];s.\mathit{backup}:=\mathit{snapshot}(\mathit{inventory});W(p_2,s);p_1\leadsto s[\mathrm{REQ}];s\to p_1[\mathrm{KO}],\\ C_{2\mathit{win}} &\triangleq s\to p_2[\mathrm{OK}];s.\mathit{backup}:=\mathit{snapshot}(\mathit{inventory});W(p_2,s);p_1\leadsto s[\mathrm{REQ}];s\to p_1[\mathrm{KO}]. \end{aligned}

Sequential composition creates a boundary of executions. Transitions never cross a sequential composition operator. This property is fundamentally important for distinguishing the delay, delay-cond, and delay-choice cases for establishing the behavioural equivalence between out-of-order executions in choreographies and parallel executions in networks § 7.

Theorem 3.1 (Execution Does Not Cross Sequential Composition). For any choreographic configuration ⟨C1∘C2,Σ,K,C⟩\langle C_1 \circ C_2, \Sigma, K, \mathcal{C}\rangle, if it can perform a μ\mu-transition and pn⁡(μ)⊆pn⁡(C1)\operatorname{pn}(\mu) \subseteq\operatorname{pn}(C_1), then there exists a choreography C1′C_1' such that ⟨C1,Σ,K,C⟩→μ⟨C1′,Σ′,K′,C⟩\langle C_1, \Sigma, K, \mathcal{C}\rangle\xrightarrow{\mu} \langle C_1', \Sigma', K', \mathcal{C}\rangle and the resulting choreographic configuration after the μ\mu-transition performed by ⟨C1∘C2,Σ,K,C⟩\langle C_1 \circ C_2, \Sigma, K, \mathcal{C}\rangle is ⟨C1′∘C2,Σ′,K′,C⟩\langle C_1' \circ C_2, \Sigma', K', \mathcal{C}\rangle.

Proof. By structural induction on the derivation of the transition. □

Messaging State Consistency and Well-Formedness

We first introduce a new concept, messaging state consistency, which specifies that all values and labels in message queues should be consumed by runtime terms. We write K⊑CK \sqsubseteq C to say KK is consistent with CC. Formally, we define messaging state consistency in Figure 7.

Figure 7. Messaging State Consistency in Nyarlathotep

We also define the standard well-formedness checks for choreographies and configurations to exclude erroneous situations such as a process communicating with itself or incorrect usage of procedure parameters. The well-formedness judgement ⟨C,{r⃗},C⟩✓\langle\mathcal{C}, \{\vec{r}\}, C\rangle\checkmark states that a choreography CC is well-formed w.r.t. a set of choreographic procedure definitions C\mathcal{C} and a set of participating processes {r⃗}\{\vec{r}\} (see appendix § 15). In particular, each communication or selection, including its runtime form, must name two distinct processes from {r⃗}\{\vec{r}\}. For each procedure call, including its runtime form, the arguments must be distinct processes from {r⃗}\{\vec{r}\}. The called procedure must be defined, and the number of arguments must match the number of parameters in its definition.

We give the formal definition of the well-formed choreographic procedure definitions C\mathcal{C} as a predicate over C\mathcal{C} and the well-formed choreographic configurations in definitions 3.2 and 3.3.

Definition 3.2 (Well-Formed Choreographic Procedure Definitions). A set of choreographic procedure definitions C\mathcal{C} is well-formed if for each X(p⃗)=CX(\vec{p}) = C in C\mathcal{C}, all processes in p⃗\vec{p} are distinct, CC does not contain any runtime terms, and ⟨K,C,{p⃗},C⟩✓\langle K, \mathcal{C}, \{\vec{p}\}, C\rangle\checkmark.

Definition 3.3 (Well-Formed Choreographic Configurations). A configuration ⟨C,Σ,K,C⟩\langle C, \Sigma, K, \mathcal{C}\rangle is well-formed if both C\mathcal{C} and CC are well-formed, and K⊑CK \sqsubseteq C.

∀p q, K(q,p)=[]K⊑0CON-ENDK⊑CK⊑p.x:=e ; CCON-LOCALK(q,p)=[]K⊑CK⊑p.e→q.x ; CCON-COMK(q,p)=v::m⃗K[(q,p)↦m⃗]⊑CK⊑p⇝q.x ; CCON-RT-COMK(q,p)=[]K⊑CK⊑p→q[L] ; CCON-SELK(q,p)=L::m⃗K[(q,p)↦m⃗]⊑CK⊑p⇝q[L] ; CCON-RT-SELK⊑(C1∘C)K⊑(C2∘C)K⊑if⁡ p.e then⁡ C1 else⁡ C2 ; CCON-CONDK⊑(C1∘C)K⊑(C2∘C)K⊑C1+pC2 ; CCON-CHOICE∀p q∈p⃗, K(q,p)=[]K⊑CK⊑X(p⃗) ; CCON-CALLK⊑CK⊑q:X(p⃗).C′ ; CCON-RT-CALL\begin{aligned} &\frac{\forall p\,q,\ K(q,p) = []}{K \sqsubseteq0} && \mathrm{CON\text{-}END}\\[6pt] &\frac{K \sqsubseteq C}{K \sqsubseteq p.x := e\,;\ C} && \mathrm{CON\text{-}LOCAL}\\[6pt] &\frac{K(q,p) = [] \qquad K \sqsubseteq C}{K \sqsubseteq p.e \to q.x\,;\ C} && \mathrm{CON\text{-}COM}\\[6pt] &\frac{K(q,p) = v :: \vec{m} \qquad K[(q,p) \mapsto\vec{m}] \sqsubseteq C}{K \sqsubseteq p \leadsto q.x\,;\ C} && \mathrm{CON\text{-}RT\text{-}COM}\\[6pt] &\frac{K(q,p) = [] \qquad K \sqsubseteq C}{K \sqsubseteq p \to q[L]\,;\ C} && \mathrm{CON\text{-}SEL}\\[6pt] &\frac{K(q,p) = L :: \vec{m} \qquad K[(q,p) \mapsto\vec{m}] \sqsubseteq C}{K \sqsubseteq p \leadsto q[L]\,;\ C} && \mathrm{CON\text{-}RT\text{-}SEL}\\[6pt] &\frac{K \sqsubseteq(C_1 \circ C) \qquad K \sqsubseteq(C_2 \circ C)}{K \sqsubseteq\operatorname{if}\ p.e\ \operatorname{then}\ C_1\ \operatorname{else}\ C_2\,;\ C} && \mathrm{CON\text{-}COND}\\[6pt] &\frac{K \sqsubseteq(C_1 \circ C) \qquad K \sqsubseteq(C_2 \circ C)}{K \sqsubseteq C_1 +_p C_2\,;\ C} && \mathrm{CON\text{-}CHOICE}\\[6pt] &\frac{\forall p\,q \in\vec{p},\ K(q,p) = [] \qquad K \sqsubseteq C}{K \sqsubseteq X(\vec{p})\,;\ C} && \mathrm{CON\text{-}CALL}\\[6pt] &\frac{K \sqsubseteq C}{K \sqsubseteq q : X(\vec{p}).C'\,;\ C} && \mathrm{CON\text{-}RT\text{-}CALL} \end{aligned}

Theorem 3.4 states that well-formedness is preserved by transitions, which is crucial for proving the behavioural equivalence between choreographies and their projections in § 7.

Theorem 3.4 (Preservation of Well-Formedness). Given a well-formed choreographic configuration ⟨C,Σ,K,G⟩\langle C, \Sigma, K, \mathcal{G} \rangle, if ⟨C,Σ,K,G⟩→μ⟨C′,Σ′,K′,G⟩\langle C, \Sigma, K, \mathcal{G} \rangle\xrightarrow{\mu} \langle C', \Sigma', K', \mathcal{G} \rangle, then ⟨C′,Σ′,K′,G⟩\langle C', \Sigma', K', \mathcal{G} \rangle is also well-formed.

Proof. By structural induction on the derivation of the transition. □

Processes and Networks

Networks are collections of endpoint programs, and endpoint programs are expressed in the process language. We adopt the syntax of the process language and networks in Mech, and design new network semantics to model nondeterminism and asynchrony.

Syntax

Figure 8 is the formal syntax of the process language. We mutually define terms PP and instructions II, and overload II for process instructions. A network is a function mapping process names to process terms, where the zero element of the codomain Process is the terminated process 00.

Syntax of the Process Language in Nyarlathotep

Figure 8. Syntax of the Process Language in Nyarlathotep

Network⁡  (Net⁡)N:PName⁡→Process⁡\operatorname{Network}\;(\operatorname{Net})\qquad N : \operatorname{PName} \to\operatorname{Process}

Since a network is a function, we establish the equality of two networks using extensional equality. Formally, for two networks NN and MM, N=MN = M if for all processes pp, N(p)=M(p)N(p) = M(p). The support supp⁡(N)\operatorname{supp}(N) consists of the processes running in NN, namely those for which N(p)≠0N(p) \ne0 (cf. § 2.3). We write N#MN \# M when their supports are disjoint. As in Mech, the terminated network 00 maps every process to 00, and the atomic network p[P]p[P] maps pp to a non-terminated process term PP and every other name to 00. Parallel composition N∣MN \mid M is left-biased and right-associative:

0(p)≜0p[P](q)≜{Pif p=q0otherwise(N∣M)(p)≜{N(p)if p∈supp⁡(N)M(p)otherwise0(p) \triangleq0 \qquad p[P](q) \triangleq\begin{cases} P & \text{if } p=q \\ 0 & \text{otherwise} \end{cases} \qquad(N \mid M)(p) \triangleq\begin{cases} N(p) & \text{if } p \in\operatorname{supp}(N) \\ M(p) & \text{otherwise} \end{cases}

Networks form a monoid under ∣\mid with identity 00 (see proposition F.2).

Semantics

We define the semantics of network configurations ⟨N,Σ,K,P⟩\langle N, \Sigma, K, \mathcal{P} \rangle as an LTS. Transitions take the form of ⟨N,Σ,K,P⟩⟶⟨N′,Σ′,K′,P⟩\langle N, \Sigma, K, \mathcal{P} \rangle\longrightarrow\langle N', \Sigma', K', \mathcal{P} \rangle, where KK is the messaging state in § 3.4, μ\mu is a transition label of the same form as in the choreographic semantics (fig. 2). This is important for establishing the behavioural equivalence between choreographies and their projected networks in § 7.

Monoidal Construction of Sequential Composition

In Figure 9 we formally define the sequential composition operation for process terms and networks, overloading the notation ▹\triangleright. We define sequential composition for networks as the pointwise extension of sequential composition for

Figure 9. Sequential Composition of Process Terms and Networks

0▹P≜P(I;P′)▹P≜I;(P′▹P)0 \triangleright P \triangleq P \qquad(I ; P') \triangleright P \triangleq I ; (P' \triangleright P)
p&{li:Pi}i∈I▹P≜p&{li:Pi▹P}i∈Ip \mathbin{\&} \{l_i : P_i\}_{i \in I} \triangleright P \triangleq p \mathbin{\&} \{l_i : P_i \triangleright P\}_{i \in I}
(N▹M)(p)≜(N(p))▹(M(p))(N \triangleright M)(p) \triangleq(N(p)) \triangleright(M(p))

process terms. The set of process terms and the set of networks each form a monoid under sequential composition. (cf. propositions F.3 and F.4).

LTS for Networks

Unlike the synchronous network semantics, the asynchronous network semantics is local. Figure 10 gives the formal semantics for networks. The rule assign models local assignments, which update the executing process’s local store. Rules send-val, recv-val, send-sel,

Semantics of Networks in Nyarlathotep

Figure 10. Semantics of Networks in Nyarlathotep

and RECV-SEL model asynchronous communication. In SEND-VAL, pp evaluates ee in its local store, appends the resulting value vv to the FIFO queue K(q,p)K(q,p), and continues with PP independently of qq. In RECV-VAL, qq removes a value vv from the head of that queue, stores it in its local variable xx, and continues with QQ. In SEND-SEL, pp appends the selection label L\mathsf{L} to the same queue and continues with PP. In RECV-SEL, when the head of the queue is a label Lj\mathsf{L}_j offered by qq, the receiver removes it and continues with the corresponding branch PjP_j.

Rules COND-THEN and COND-ELSE select P1P_1 if the local guard evaluates to true and P2P_2 otherwise. Both rules then append the continuation QQ. Rules CHOICE-L and CHOICE-R resolve a local nondeterministic choice by taking a transition of one of its branches. If PP makes a μ\mu-transition to P′P' and p∈pn⁡(μ)p \in\operatorname{pn}(\mu), CHOICE-L resolves the choice to the left branch and continues with P′&RP' \mathbin{\&} R. Similarly, with a transition from QQ to Q′Q', CHOICE-R resolves the choice to the right branch and continues with Q′&RQ' \mathbin{\&} R. Both rules retain the store and queue updates from the branch transition. The projected reusable lock in example 1.2 illustrates how a receive can resolve a choice in the same step. If both requests are queued, the server can resolve its choice by receiving either one.

The rule CHOICE-SKIP is the network counterpart of the choreographic garbage collection rules SKIP-L and SKIP-R. It lets the process proceed directly to the continuation when both branches are terminated. Rule CALL models recursions. It substitutes the actual process names for the parameters in the procedure body and appends the caller’s continuation. We again write P[q⃗/r⃗]P[\vec{q}/\vec{r}] for substituting process names in PP (cf. definition B.4). Rule PAR models parallel executions of disjoint networks. It allows one part of a network to make a transition while the other processes remain unaffected.

A Comparison of Synchrony and Asynchrony in the Presence of Nondeterminism

In this section we compare how nondeterminism interacts with synchrony and asynchrony: we show that the former requires a cumbersome semantics and can express fewer behaviours, and we identify the lack of locality introduced by synchrony as the root cause.

Synchrony complicates the semantics of nondeterministic choice. In Mech, a synchronous communication resolves the choices leading to the send and receive in a single synchronised transition, resulting in the non-local semantics in Figure 11. We show how nested choices is handled in example 5.1.

Choice rules for choreographies and networks in Mech

Figure 11. Modelling Nondeterminism with Synchrony: Choice Rules for Choreographies and Networks in Mech

Example 5.1 (Nested Choreographic Choices and Their Projected Network). Although the following choreographies CpqC_{\mathrm{pq}} and CqpC_{\mathrm{qp}} have different nesting structures:

Cpq≜(p.1→q.x+qp.1→q.y)+p(p.2→q.x+qp.2→q.y)C_{\mathrm{pq}} \triangleq(p.1 \to q.x +_{q} p.1 \to q.y) +_{p} (p.2 \to q.x +_{q} p.2 \to q.y)
Cqp≜(p.1→q.x+pp.2→q.x)+q(p.1→q.y+pp.2→q.y),C_{\mathrm{qp}} \triangleq(p.1 \to q.x +_{p} p.2 \to q.x) +_{q} (p.1 \to q.y +_{p} p.2 \to q.y),

they should exhibit the same behaviour, because they are projected into the same network NN:

N≜p[q!1+q!2]∣q[p?x+p?y].N \triangleq p[q!1 + q!2] \mathbin{|} q[p?x + p?y].

Suppose pp chooses left and qq chooses right in one transition. In Mech the derivation for CpqC_{\mathrm{pq}} resolves the choice at qq before the choice at pp, while the derivation for CqpC_{\mathrm{qp}} resolves them in the opposite order. For EPP soundness, both derivations must have the same label, which also matches the corresponding transition of their common projected network. To give these derivations the same label, Mech pairs the communication label with a choice map from process names to lists of branch choices, as discussed in § 3.2.1. Mech’s CHOICE-L and CHOICE-R rules record the selected branch in the choice map for the process resolving the choice.

Updates for distinct processes commute, so the two derivations produce the same label.

⟨Cpq,Σ,C⟩→(p.1→q.addChoice⁡ q right⁡).addChoice⁡ p left⁡⟨0,Σ[q.y↦1],C⟩\langle C_{pq}, \Sigma, \mathcal{C} \rangle\xrightarrow{(p.1\to q.\operatorname{addChoice}\ q\ \operatorname{right}).\operatorname{addChoice}\ p\ \operatorname{left}} \langle0, \Sigma[q.y \mapsto1], \mathcal{C} \rangle
⟨Cqp,Σ,C⟩→(p.1→q.addChoice⁡ p left⁡).addChoice⁡ q right⁡⟨0,Σ[q.y↦1],C⟩.\langle C_{qp}, \Sigma, \mathcal{C} \rangle\xrightarrow{(p.1\to q.\operatorname{addChoice}\ p\ \operatorname{left}).\operatorname{addChoice}\ q\ \operatorname{right}} \langle0, \Sigma[q.y \mapsto1], \mathcal{C} \rangle.

The network rules encode the synchronisation obligation of nondeterministic behaviours in communication by requiring a compatible joint step and recording the choices resolved in it:

⟨N,Σ,P⟩→(p.1→q.addChoice⁡ p left⁡).addChoice⁡ q right⁡⟨p[0]∣q[0],Σ[q.y↦1],P⟩.\langle N, \Sigma, \mathcal{P} \rangle\xrightarrow{(p.1\to q.\operatorname{addChoice}\ p\ \operatorname{left}).\operatorname{addChoice}\ q\ \operatorname{right}} \langle p[0]\mathbin{|}q[0], \Sigma[q.y \mapsto1], \mathcal{P} \rangle.

By contrast, the operational semantics of Nyarlathotep satisfies the locality property: each transition has a single active process. We split communication into separate send and receive steps. Each process follows its own program and communicates through the queue in the messaging state. In the Nyarlathotep transitions, given K0(q,p)=[]K_0(q,p) = [], p resolves its choice when it sends, and q resolves its choice when it receives. Each label therefore needs only one list of branch choices.

⟨Cpq,Σ,K0,C⟩→left⁡@p::p.1→q!⟨p⇝q.x+qp⇝q.y,Σ,K0[(q,p)↦[1]],C⟩\langle C_{pq}, \Sigma, K_0, \mathcal{C} \rangle\xrightarrow{\operatorname{left}@p::p.1\to q!} \langle p\mathbin{\leadsto}q.x +_q p\mathbin{\leadsto}q.y, \Sigma, K_0[(q,p)\mapsto[1]], \mathcal{C} \rangle
⟨Cqp,Σ,K0,C⟩→left⁡@p::p.1→q!⟨p⇝q.x+qp⇝q.y,Σ,K0[(q,p)↦[1]],C⟩\langle C_{qp}, \Sigma, K_0, \mathcal{C} \rangle\xrightarrow{\operatorname{left}@p::p.1\to q!} \langle p\mathbin{\leadsto}q.x +_q p\mathbin{\leadsto}q.y, \Sigma, K_0[(q,p)\mapsto[1]], \mathcal{C} \rangle
⟨p⇝q.x+qp⇝q.y,Σ,K0[(q,p)↦[1]],C⟩→right⁡@q::p.1→q?⟨0,Σ[q.y↦1],K0,C⟩.\langle p\mathbin{\leadsto}q.x +_q p\mathbin{\leadsto}q.y, \Sigma, K_0[(q,p)\mapsto[1]], \mathcal{C} \rangle\xrightarrow{\operatorname{right}@q::p.1\to q?} \langle0, \Sigma[q.y\mapsto1], K_0, \mathcal{C} \rangle.

And the network transitions are:

⟨N,Σ,K0,P⟩→left⁡@p::p.1→q!⟨p[0]∣q[p?x+p?y],Σ,K0[(q,p)↦[1]],P⟩\langle N, \Sigma, K_0, \mathcal{P} \rangle\xrightarrow{\operatorname{left}@p::p.1\to q!} \langle p[0]\mathbin{|}q[p?x + p?y], \Sigma, K_0[(q,p)\mapsto[1]], \mathcal{P} \rangle
→right⁡@q::p.1→q?⟨p[0]∣q[0],Σ[q.y↦1],K0,P⟩.\xrightarrow{\operatorname{right}@q::p.1\to q?} \langle p[0]\mathbin{|}q[0], \Sigma[q.y\mapsto1], K_0, \mathcal{P} \rangle.

Synchrony expresses fewer behaviours. With Nyarlathotep, in the execution of the reusable lock (example 1.1) shown in § 3, p₁ sends its request before p₂. The requests enter separate queues, and the server s in fact receives p₂’s request first, granting the lock to p₂. In Mech, sending a request and receiving it at s form a single synchronised transition. If p₁ sends first, s receives that request in the same transition, resolving the choice in favour of p₁. Thus Mech ties the winner to the first client to communicate its request. Using the same shorthand C1C_1 and C2C_2 for branches from § 3, one unfolded iteration of the lock takes the following transitions:

⟨(C1+sC2);X(s,p1,p2),Σ,C⟩→p1→s[req].addChoice⁡ sleft⟨s→p1[ok];s.backup:=snapshot(inventory);W(p1,s);p2→s[req];s→p2[ko];X(s,p1,p2),Σ,C⟩\left\langle(C_1 +_s C_2); X(s,p_1,p_2), \Sigma, \mathcal{C} \right\rangle \xrightarrow{p_1 \to_s [\mathrm{req}].\operatorname{addChoice}\ \mathrm{sleft}} \left\langle s \to p_1[\mathrm{ok}];s.\mathit{backup}:=\mathit{snapshot}(\mathit{inventory});W(p_1,s);p_2 \to_s[\mathrm{req}];s \to p_2[\mathrm{ko}];X(s,p_1,p_2),\Sigma,\mathcal{C} \right\rangle

Endpoint Projection (EPP)

EPP compiles choreographies into networks. A central concern in the design of EPP is handling knowledge of choice (KoC). We address this using the select-and-merge approach. Since our network language presents new semantics while leaving the syntax of the process terms and networks unchanged, we reuse the merge operation (⊔\sqcup) from Mech, as described in § 2.2.

Process Projection and EPP

We define EPP using the process projection, which produces the local program for a given process specified in a choreography. Process projection is a function of the type:

⟦⋅⟧_:Chor→PName→Process?\llbracket\cdot\rrbracket_{\_} : \mathit{Chor} \to\mathit{PName} \to\mathit{Process?}

In Figure 12, we show the algorithm of process projection. A terminated choreography projects to a terminated process. We project a sequence I ; CI\,;\,C by first projecting the choreographic instruction II. When II is a local assignment, we project it to an assignment at the same process. A communication projects to a send and a receive, and a selection projects to a selection instruction and a branching term. For the runtime instructions p⇝q.xp \leadsto q.x and p⇝q[l]p \leadsto q[l], pp has already sent the value or label. We therefore project only the pending action at qq, a receive into xx or a branching term, respectively.

Process Projection of Choreographies in Nyarlathotep

Figure 12. Process Projection of Choreographies in Nyarlathotep

⟦0⟧r≜⟨0⟩⟦p.x:=e ; C⟧r≜{⟨x:=e ; P⟩if r=p and ⟦C⟧r=⟨P⟩⟦C⟧rotherwise\begin{aligned} \llbracket0 \rrbracket_r &\triangleq\langle0 \rangle\\ \llbracket p.x := e\,;\,C \rrbracket_r &\triangleq \begin{cases} \langle x := e\,;\,P \rangle& \text{if } r=p \text{ and } \llbracket C \rrbracket_r=\langle P\rangle\\ \llbracket C \rrbracket_r & \text{otherwise} \end{cases} \end{aligned}
⟦p.e→q.x ; C⟧r≜{⟨q!e ; P⟩if r=p and ⟦C⟧r=⟨P⟩⟨p?x ; P⟩if r=q and ⟦C⟧r=⟨P⟩⟦C⟧rotherwise\llbracket p.e \to q.x\,;\,C \rrbracket_r \triangleq \begin{cases} \langle q!e\,;\,P\rangle& \text{if } r=p \text{ and } \llbracket C \rrbracket_r=\langle P\rangle\\ \langle p?x\,;\,P\rangle& \text{if } r=q \text{ and } \llbracket C \rrbracket_r=\langle P\rangle\\ \llbracket C \rrbracket_r & \text{otherwise} \end{cases}
⟦p⇝q.x ; C⟧r≜{⟨p?x ; P⟩if r=q and ⟦C⟧r=⟨P⟩⟦C⟧rotherwise\llbracket p \leadsto q.x\,;\,C \rrbracket_r \triangleq \begin{cases} \langle p?x\,;\,P\rangle& \text{if } r=q \text{ and } \llbracket C \rrbracket_r=\langle P\rangle\\ \llbracket C \rrbracket_r & \text{otherwise} \end{cases}
⟦p→q[l] ; C⟧r≜{⟨q⊕l ; P⟩if r=p and ⟦C⟧r=⟨P⟩⟨p&{l:P}⟩if r=q and ⟦C⟧r=⟨P⟩⟦C⟧rotherwise\llbracket p \to q[l]\,;\,C \rrbracket_r \triangleq \begin{cases} \langle q \oplus l\,;\,P\rangle& \text{if } r=p \text{ and } \llbracket C \rrbracket_r=\langle P\rangle\\ \langle p \& \{l:P\}\rangle& \text{if } r=q \text{ and } \llbracket C \rrbracket_r=\langle P\rangle\\ \llbracket C \rrbracket_r & \text{otherwise} \end{cases}
⟦p⇝q[l] ; C⟧r≜{⟨p&{l:P}⟩if r=q and ⟦C⟧r=⟨P⟩⟦C⟧rotherwise\llbracket p \leadsto q[l]\,;\,C \rrbracket_r \triangleq \begin{cases} \langle p \& \{l:P\}\rangle& \text{if } r=q \text{ and } \llbracket C \rrbracket_r=\langle P\rangle\\ \llbracket C \rrbracket_r & \text{otherwise} \end{cases}
⟦if p.e then C1 else C2 ; C⟧r≜{⟨if e then P1 else P2 ; P⟩if r=p and ⟦C1⟧r=⟨P1⟩ and ⟦C2⟧r=⟨P2⟩ and ⟦C⟧r=⟨P⟩⟨Q▹P⟩if r≠p and ⟦C1⟧r⊔⟦C2⟧r=⟨Q⟩ and ⟦C⟧r=⟨P⟩⟨⟩otherwise\llbracket\mathsf{if}\ p.e\ \mathsf{then}\ C_1\ \mathsf{else}\ C_2\,;\,C \rrbracket_r \triangleq \begin{cases} \langle\mathsf{if}\ e\ \mathsf{then}\ P_1\ \mathsf{else}\ P_2\,;\,P\rangle& \text{if } r=p \text{ and } \llbracket C_1\rrbracket_r=\langle P_1\rangle\text{ and } \llbracket C_2\rrbracket_r=\langle P_2\rangle\text{ and } \llbracket C\rrbracket_r=\langle P\rangle\\ \langle Q \mathbin{\triangleright} P\rangle& \text{if } r\ne p \text{ and } \llbracket C_1\rrbracket_r\sqcup\llbracket C_2\rrbracket_r=\langle Q\rangle\text{ and } \llbracket C\rrbracket_r=\langle P\rangle\\ \langle\rangle& \text{otherwise} \end{cases}
⟦C1+pC2 ; C⟧r≜{⟨P1+P2 ; P⟩if r=p and ⟦C1⟧r=⟨P1⟩ and ⟦C2⟧r=⟨P2⟩ and ⟦C⟧r=⟨P⟩⟨Q▹P⟩if r≠p and ⟦C1⟧r⊔⟦C2⟧r=⟨Q⟩ and ⟦C⟧r=⟨P⟩⟨⟩otherwise\llbracket C_1 +_p C_2\,;\,C \rrbracket_r \triangleq \begin{cases} \langle P_1+P_2\,;\,P\rangle& \text{if } r=p \text{ and } \llbracket C_1\rrbracket_r=\langle P_1\rangle\text{ and } \llbracket C_2\rrbracket_r=\langle P_2\rangle\text{ and } \llbracket C\rrbracket_r=\langle P\rangle\\ \langle Q \mathbin{\triangleright} P\rangle& \text{if } r\ne p \text{ and } \llbracket C_1\rrbracket_r\sqcup\llbracket C_2\rrbracket_r=\langle Q\rangle\text{ and } \llbracket C\rrbracket_r=\langle P\rangle\\ \langle\rangle& \text{otherwise} \end{cases}
⟦X(p⃗) ; C⟧r≜{⟨Xi(p⃗∖r) ; P⟩if r=pi for p⃗=p1,…,pn and 1≤i≤n and ⟦C⟧r=⟨P⟩⟦C⟧rotherwise\llbracket X(\vec{p})\,;\,C \rrbracket_r \triangleq \begin{cases} \langle X_i(\vec{p}\setminus r)\,;\,P\rangle& \text{if } r=p_i \text{ for } \vec{p}=p_1,\ldots,p_n \text{ and } 1\le i\le n \text{ and } \llbracket C\rrbracket_r=\langle P\rangle\\ \llbracket C\rrbracket_r & \text{otherwise} \end{cases}
⟦q:X(p⃗).C′ ; C⟧r≜{⟨Xi(p⃗∖r) ; P′⟩if r=q=pi for p⃗=p1,…,pn, 1≤i≤n, and ⟦C′⟧r=⟨P′⟩⟦C⟧rotherwise\llbracket q:X(\vec{p}).C'\,;\,C \rrbracket_r \triangleq \begin{cases} \langle X_i(\vec{p}\setminus r)\,;\,P'\rangle& \text{if } r=q=p_i \text{ for } \vec{p}=p_1,\ldots,p_n,\ 1\le i\le n,\ \text{and } \llbracket C'\rrbracket_r=\langle P'\rangle\\ \llbracket C\rrbracket_r & \text{otherwise} \end{cases}

In each case, the projection of CC provides the continuation. At processes with no action for II, we project only CC.

A conditional projects to a local conditional with the same guard expression at the guard process. A choreographic choice projects to a nondeterministic choice at the choice-resolving process. At each other process, we merge the projections of the two branches. We then append the projection of CC. If a required projection or merge yields ⟨⟩\langle\rangle, the result is ⟨⟩\langle\rangle. To project a choreographic procedure call onto a participating process pp, we use its position ii in the argument list to obtain the local procedure XiX_i. The projected call takes the other participating processes as arguments. After the call, pp continues with its part of CC, indicated by ⟦C⟧p\llbracket C\rrbracket_p. In the runtime term q:X(p⃗).C′;Cq:X(\vec{p}).C';C, only qq has yet to enter the call, so we project the local call there and use the projection of C′C' as its continuation. Otherwise, we project only CC.

A choreography CC is projectable onto a process rr if ⟦C⟧r=⟨P⟩\llbracket C\rrbracket_r=\langle P\rangle for some process term PP. If ⟦C⟧r=⟨⟩\llbracket C\rrbracket_r=\langle\rangle, then CC is not projectable onto a process rr. We define EPP of choreographies as ⟦⋅⟧:Chor→Net?\llbracket\cdot\rrbracket:\mathrm{Chor}\to\mathbf{Net}? in Figure 13a. If CC is projectable onto every process in pn⁡(C)\operatorname{pn}(C), its EPP is a network mapping each such process to its projected process term and all other processes to 00. Otherwise, the result is ⟨⟩\langle\rangle. In general, ⟦⋅⟧p\llbracket\cdot\rrbracket_p and ⟦⋅⟧\llbracket\cdot\rrbracket are homomorphisms of a monoid. This property is crucial for establishing the correctness of EPP concerning KoC, nondeterminism, and out-of-order executions. In Nyarlathotep, we show that ⟦⋅⟧p\llbracket\cdot\rrbracket_p and ⟦⋅⟧\llbracket\cdot\rrbracket are distributive over §\mathbin{\S} in proposition 6.1.

⟦C⟧≜{⟨p↦Pp⟩if ⟦C⟧p=⟨Pp⟩ for each p∈pn⁡(C) and Pp=0 for each p∉pn⁡(C)⟨⟩if there exists p∈pn⁡(C) such that ⟦C⟧p=⟨⟩\llbracket C\rrbracket\triangleq \begin{cases} \langle p \mapsto P_p\rangle& \text{if }\llbracket C\rrbracket_p=\langle P_p\rangle\text{ for each }p\in\operatorname{pn}(C)\text{ and }P_p=0\text{ for each }p\notin\operatorname{pn}(C)\\ \langle\rangle& \text{if there exists }p\in\operatorname{pn}(C)\text{ such that }\llbracket C\rrbracket_p=\langle\rangle \end{cases}

(a) Endpoint Projection for Choreographies

⟦C⟧≜{⟨{Xi(p⃗∖pi)=Ppi}⟩if for each X(p⃗)=C∈C, ⟦C⟧pi=⟨Ppi⟩ and pi∈p⃗⟨⟩if for any X(p⃗)=C∈C, there exists a p∈p⃗ such that ⟦C⟧p=⟨⟩\llbracket\mathcal{C}\rrbracket\triangleq \begin{cases} \langle\{X_i(\vec{p}\setminus p_i)=P_{p_i}\}\rangle& \text{if for each }X(\vec{p})=C\in\mathcal{C},\ \llbracket C\rrbracket_{p_i}=\langle P_{p_i}\rangle\text{ and }p_i\in\vec{p}\\ \langle\rangle& \text{if for any }X(\vec{p})=C\in\mathcal{C},\text{ there exists a }p\in\vec{p}\text{ such that }\llbracket C\rrbracket_p=\langle\rangle \end{cases}

(b) Endpoint Projection for Choreographic Procedure Definitions

Figure 13. Definitions of Endpoint Projection

Proposition 6.1 (Distributivity of Process Projection and EPP over §\mathbin{\S}). For any choreography C1C_1 and C2C_2, and any process pp:

⟦C1§C2⟧p=⟦C1⟧p§⟦C2⟧pand⟦C1§C2⟧=⟦C1⟧§⟦C2⟧.\llbracket C_1 \mathbin{\S} C_2\rrbracket_p=\llbracket C_1\rrbracket_p\mathbin{\S}\llbracket C_2\rrbracket_p \quad\text{and}\quad \llbracket C_1 \mathbin{\S} C_2\rrbracket=\llbracket C_1\rrbracket\mathbin{\S}\llbracket C_2\rrbracket.

In Figure 13b, we define the EPP for sets of procedure definitions. We overload the notation and write it as ⟦C⟧\llbracket\mathcal{C}\rrbracket, which is a function of the type: ⟦⋅⟧:C→P?\llbracket\cdot\rrbracket:\mathcal{C}\to\mathbb{P}?. A choreographic procedure with nn process parameters generates nn process procedures, one for the perspective of each parameter. If any procedure body is not projectable onto one of its process parameters, the result is ⟨⟩\langle\rangle.

Coherence

We define coherence between a choreography and choreographic procedure definitions for handling recursion correctly. It ensures the consistency of projection for partially entered procedure calls. For a runtime call q:X(p⃗).C′;Cq:X(\vec{p}).C';C, rule \textsc{coh-rtcall} (Figure 14) requires that the projection onto qq of the unfolded call followed by C′C' has at least the branches of the projection of CC onto qq. The two additional rules for Nyarlathotep, \textsc{coh-rtcom} and \textsc{coh-rtsel}, simply require a coherent continuation (cf. section 6.2). As with well-formedness, choreographic transitions preserve coherence.

Image not extracted

Figure 14. Coherence of Choreographies (The Rule for Runtime Terms)

Theorem 6.2 (Preservation of Coherence). For any well-formed choreographic configuration ⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle in which CC and C\mathcal{C} are both projectable and CαCC\mathrel{\alpha}\mathcal{C}, if ⟨C,Σ,K,C⟩→μ⟨C′,Σ′,K′,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\mu} \langle C',\Sigma',K',\mathcal{C}\rangle, then the resulting choreography C′C' is still coherent w.r.t. C\mathcal{C}, i.e., C′αCC'\mathrel{\alpha}\mathcal{C}.

CαCCαC′X(s⃗)=C′′∈C∣p∣=∣s⃗∣⟦C′′[p⃗/s⃗]⟧q=⟨P⟩⟦C⟧q=⟨Q⟩⟨P⟩⊑⟨Q⟩\mathcal{C}\mathrel{\alpha}C\quad\mathcal{C}\mathrel{\alpha}C'\quad X(\vec{s})=C''\in\mathcal{C}\quad|p|=|\vec{s}|\quad\llbracket C''[\vec{p}/\vec{s}]\rrbracket_q=\langle P\rangle\quad\llbracket C\rrbracket_q=\langle Q\rangle\quad\langle P\rangle\sqsubseteq\langle Q\rangle
\frac{\mathcal{C}\mathrel{\alpha}q:X(\vec{p}).C';C}{\mathcal{C}\mathrel{\alpha}q:X(\vec{p}).C';C}\ \textsc{coh-rtcall}

Proof. By structural induction on the derivation of the transition.

Correctness of EPP

We establish the correctness of EPP by showing that choreographies and their projected networks can match each other’s transitions. We first prove completeness and soundness for single-step transitions and then extend both results to multi-step executions. The main challenge is to track the dependencies that arise when choreographic nondeterminism, asynchrony, out-of-order execution, and general branching interact, so that each alternative behaviour can be matched in the other semantics. The locality property of Nyarlathotep’s semantics enables a compositional approach to proving the correctness of EPP. Each network transition involves a single active process, whose behaviour we analyse separately from the rest of the network. For the unaffected processes, we show that the simulation relation still holds between the resulting network and the projection of the resulting choreography after the matching transitions.

Completeness and Soundness of EPP

The completeness in theorem 7.1 says that all networks resulting for EPP are complete implementations of their corresponding choreographies: for every choreographic transition, there is a corresponding network transition whose resulting network is related by the simulation relation (⊒\sqsupseteq) to the projection of the resulting choreography.

The novelty of our reasoning approach is to introduce a localised semantics for the process language (appendix § 19). It describes a local transition at an active process pp in the form ⟨P,Σ,K,P⟩→μp⟨P′,Σ′,K′,P′⟩\langle P, \Sigma, K, \mathcal{P} \rangle\xrightarrow{\mu}_{p} \langle P', \Sigma', K', \mathcal{P}' \rangle. We then establish conversions between localised and network transitions (lemmas G.1 to G.3). Together with the lax compatibility of merge at the active process (theorem L.4), they allow us to match choreographic transitions with network transitions by analysing the active process’s local transition and composing it with the unaffected part of the projected network.

Theorem 7.1 (Completeness of EPP). Given a choreographic configuration ⟨C,Σ,K,C⟩\langle C, \Sigma, K, \mathcal{C} \rangle that is well-formed, where C∝CC \propto\mathcal{C}, ⟦C⟧=⟨N⟩\llbracket C \rrbracket= \langle N \rangle, and ⟦C⟧=⟨P⟩\llbracket\mathcal{C} \rrbracket= \langle\mathcal{P} \rangle, for any transition label μ\mu, if ⟨C,Σ,K,C⟩→μ⟨C′,Σ′,K′,C′⟩\langle C, \Sigma, K, \mathcal{C} \rangle\xrightarrow{\mu} \langle C', \Sigma', K', \mathcal{C}' \rangle, then there exist networks N′N' and M′M' such that ⟨N,Σ,K,P⟩→μ⟨N′,Σ′,K′,P′⟩\langle N, \Sigma, K, \mathcal{P} \rangle\xrightarrow{\mu} \langle N', \Sigma', K', \mathcal{P}' \rangle, ⟦C′⟧=⟨M′⟩\llbracket C' \rrbracket= \langle M' \rangle, and N′⊒M′N' \sqsupseteq M'.

Proof. By induction on the transition derivation, using lemmas G.3, G.1 and theorem L.4.

The soundness in § 7.2 is the converse of the completeness: every network resulting from EPP is a sound implementation of its corresponding choreography, and every transition of NN is prescribed by CC, with the resulting network retaining the simulation relation. We give the formal definition in theorem 7.2. We require N⊒MN \sqsupseteq M for the generalisation to multi-step transitions (§ 7.2). Completeness starts from a choreographic transition whose message queue premises already hold, while the soundness proof need to use message queue consistency to ensure that a network receive matches a pending receive in the choreography. To structure the queue consistency argument, we define the transition relation K→μK′K \xrightarrow{\mu} K' for messaging states in appendix § 20. We can then replace the messaging states of a transition when applying the induction hypothesis to the continuation. We use lemma H.1 to isolate a messaging state transition from a network transition.

Theorem 7.2 (Soundness of EPP). Given a choreographic configuration ⟨C,Σ,K,C⟩\langle C, \Sigma, K, \mathcal{C} \rangle that is well-formed, where C∝CC \propto\mathcal{C}, ⟦C⟧=⟨M⟩\llbracket C \rrbracket= \langle M \rangle, and ⟦C⟧=⟨P⟩\llbracket\mathcal{C} \rrbracket= \langle\mathcal{P} \rangle, for any networks NN, N′N', and transition label μ\mu where N⊒MN \sqsupseteq M, if ⟨N,Σ,K,P⟩→μ⟨N′,Σ′,K′,P′⟩\langle N, \Sigma, K, \mathcal{P} \rangle\xrightarrow{\mu} \langle N', \Sigma', K', \mathcal{P}' \rangle, then there exists a choreography C′C' and a network M′M' such that ⟨C,Σ,K,C⟩→μ⟨C′,Σ′,K′,C′⟩\langle C, \Sigma, K, \mathcal{C} \rangle\xrightarrow{\mu} \langle C', \Sigma', K', \mathcal{C}' \rangle, ⟦C′⟧=⟨M′⟩\llbracket C' \rrbracket= \langle M' \rangle, and N′⊒M′N' \sqsupseteq M'.

Proof. By induction on the choreography CC. By lemma G.3, we identify the active process and use its local transition to derive the matching choreographic step. For steps delayed past a pending receive, lemmas H.1 to H.3 justify applying the induction hypothesis with the continuation’s messaging states and then restoring the original messaging states. For delayed conditionals and choices, proposition 6.1 and theorem 3.1 relate the branch transitions to their continuation. □

Correctness of Multi-Step Executions

We use a standard transitive closure to define the multi-step transitions for both choreographies and networks, written as ⟨C,Σ,K,C⟩→μ⃗⟨C′,Σ′,K′,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\vec{\mu}} \langle C',\Sigma',K',\mathcal{C}\rangle and ⟨N,Σ,K,P⟩→μ⃗⟨N′,Σ′,K′,P⟩\langle N,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\vec{\mu}} \langle N',\Sigma',K',\mathcal{P}\rangle. The sequence μ⃗\vec{\mu} is a list of transition labels that can be empty. The detailed definitions are shown in appendix N. We show the correctness of EPP for multi-step executions by the completeness theorem 7.3 and soundness theorem 7.4:

Theorem 7.3 (Completeness of Multi-Step Executions). Let ⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle be a well-formed choreographic configuration, where C∝CC \propto\mathcal{C}, ⟦C⟧=⟨N⟩\llbracket C\rrbracket= \langle N\rangle, and ⟦C⟧=⟨P⟩\llbracket\mathcal{C}\rrbracket= \langle\mathcal{P}\rangle, for any list of transition labels μ⃗\vec{\mu}, if ⟨C,Σ,K,C⟩→μ⃗⟨C′,Σ′,K′,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\vec{\mu}} \langle C',\Sigma',K',\mathcal{C}\rangle, then there exists networks N′N' and M′M' such that ⟨N,Σ,K,P⟩→μ⃗⟨N′,Σ′,K′,P⟩\langle N,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\vec{\mu}} \langle N',\Sigma',K',\mathcal{P}\rangle, ⟦C′⟧=⟨M′⟩\llbracket C'\rrbracket= \langle M'\rangle, and N′⊒M′N' \sqsupseteq M'.

Theorem 7.4 (Soundness of Multi-Step Executions). Let ⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle be a well-formed choreographic configuration with C∝CC \propto\mathcal{C}, ⟦C⟧=⟨M⟩\llbracket C\rrbracket= \langle M\rangle, and ⟦C⟧=⟨P⟩\llbracket\mathcal{C}\rrbracket= \langle\mathcal{P}\rangle. For any networks NN, N′N' and any list μ⃗\vec{\mu} of transition labels, if N⊒MN \sqsupseteq M and ⟨N,Σ,K,P⟩→μ⃗⟨N′,Σ′,K′,P⟩\langle N,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\vec{\mu}} \langle N',\Sigma',K',\mathcal{P}\rangle, then there exist a choreography C′C' and a network M′M' such that ⟨C,Σ,K,C⟩→μ⃗⟨C′,Σ′,K′,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\vec{\mu}} \langle C',\Sigma',K',\mathcal{C}\rangle, ⟦C′⟧=⟨M′⟩\llbracket C'\rrbracket= \langle M'\rangle, and N′⊒M′N' \sqsupseteq M'.

We prove both theorems by induction on the derivation of the multi-step transition. We use the completeness and soundness theorems 7.1 and 7.2, the preservation of well-formedness (theorem 3.4), coherence (theorem 6.2), and simulation relation (theorem D.3).

The Correctness of EPP Guarantees Safety and Liveness Properties

The correctness of EPP guarantees important safety and liveness properties of networks projected from choreographies. We establish communication safety in § 8.1 and deadlock freedom in § 8.2. In an asynchronous system, the sender can proceed once it places a message in the receiver’s queue, while the corresponding receive remains pending. Establishing communication safety and deadlock freedom is thus more involved than in the synchronous setting, since we must also reason about which messages are queued and when they can be received.

Communication Safety

Communication safety is an important safety property of communicating processes. It ensures the absence of mismatched communications. A mismatch occurs, for instance, when a receiver expects a value but the message to be received is a selection label.

Figure 15 defines communication actions and their duals, and fig. 16 gives the enabled communication actions of a process term for a given process. We characterise communication-safe states in definition 8.2 by checking whether the sender’s and receiver’s enabled actions are compatible given the contents of their message queue. We define this compatibility in definition 8.1.

Communication Action (Act): $\alpha ::= \mathord{!}\mid\mathord{?}\mid\oplus_{\mathrm{L}}\mid\&_{\mathrm{L}}$; $\overline{!}\triangleq ?$, $\overline{?}\triangleq !$, $\overline{\oplus_{\mathrm{L}}}\triangleq\&_{\mathrm{L}}$, $\overline{\&_{\mathrm{L}}}\triangleq\oplus_{\mathrm{L}}$

Figure 15. Communication Actions and Their Duals

0⊛p≜∅x:=e ; P⊛p≜∅X(q⃗) ; P⊛p≜∅if e then P1 else P2 ; P⊛p≜∅P1+P2 ; P⊛p≜P1⊛p∪P2⊛pq!e ; P⊛p≜{{!}if p=q∅otherwiseq?x ; P⊛p≜{{?}if p=q∅otherwiseq⊕L ; P⊛p≜{{⊕L}if p=q∅otherwiseq&{Li:Pi}i∈I⊛p≜{{&Li}i∈Iif p=q∅otherwise\begin{aligned} 0 \mathbin{\circledast} p &\triangleq\varnothing& x := e\,;\,P \mathbin{\circledast} p &\triangleq\varnothing& X(\vec{q})\,;\,P \mathbin{\circledast} p &\triangleq\varnothing\\ \mathbf{if}\ e\ \mathbf{then}\ P_1\ \mathbf{else}\ P_2\,;\,P \mathbin{\circledast} p &\triangleq\varnothing& P_1 + P_2\,;\,P \mathbin{\circledast} p &\triangleq P_1 \mathbin{\circledast} p \cup P_2 \mathbin{\circledast} p \\ q!e\,;\,P \mathbin{\circledast} p &\triangleq\begin{cases} \{!\} & \text{if } p=q \\ \varnothing& \text{otherwise} \end{cases} & q?x\,;\,P \mathbin{\circledast} p &\triangleq\begin{cases} \{?\} & \text{if } p=q \\ \varnothing& \text{otherwise} \end{cases} \\ q\oplus L\,;\,P \mathbin{\circledast} p &\triangleq\begin{cases} \{\oplus_L\} & \text{if } p=q \\ \varnothing& \text{otherwise} \end{cases} & q\mathbin{\&}\{L_i:P_i\}_{i\in I}\mathbin{\circledast}p &\triangleq\begin{cases} \{\mathbin{\&}L_i\}_{i\in I} & \text{if } p=q \\ \varnothing& \text{otherwise} \end{cases} \end{aligned}

Fig. 16. Enabled Communication Actions

Definition 8.1 (Message Queue Compatibility). Consider the message queue and two sets of communication actions, one for the receiver and one for the sender. When the queue is non-empty, the sets are compatible if and only if the receiver’s set is input compatible with the pending receive for the message at the head of the queue. The pending receive is ?? for a value and &l\mathbin{\&}l for a selection label ll. When the queue is empty, the sets are compatible if and only if the receiver’s set is input compatible with α‾\overline{\alpha} for every value send or label selection α\alpha in the sender’s set.

Definition 8.2 (Communication-Safe State). A network NN is communication safe at a messaging state KK if and only if, for every ordered pair of distinct processes pp and qq, the enabled actions N(q)⊛pN(q)\mathbin{\circledast}p of the receiver and N(p)⊛qN(p)\mathbin{\circledast}q of the sender are compatible for the message queue K(q,p)K(q,p). A network configuration ⟨N,Σ,K,P⟩\langle N,\Sigma,K,\mathcal{P}\rangle is communication safe if and only if NN is communication safe at KK.

Theorem 8.3 (Communication Safety). Let ⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle be a well-formed choreographic configuration, where C∝CC \propto\mathcal{C}, ⟦C⟧=⟨N⟩\llbracket C\rrbracket=\langle N\rangle, and ⟦C⟧=⟨P⟩\llbracket\mathcal{C}\rrbracket=\langle\mathcal{P}\rangle. If ⟨N,Σ,K,P⟩→μ∗⟨N′,Σ′,K′,P⟩\langle N,\Sigma,K,\mathcal{P}\rangle\mathrel{\xrightarrow{\mu}^{*}} \langle N',\Sigma',K',\mathcal{P}\rangle, then ⟨N′,Σ′,K′,P⟩\langle N',\Sigma',K',\mathcal{P}\rangle is communication safe.

Proof. By theorem 7.4, the network execution is matched by ⟨C,Σ,K,C⟩→μ∗⟨C′,Σ′,K′,C′⟩\langle C,\Sigma,K,\mathcal{C}\rangle\mathrel{\xrightarrow{\mu}^{*}} \langle C',\Sigma',K',\mathcal{C}'\rangle with ⟦C′⟧=⟨M′⟩\llbracket C'\rrbracket=\langle M'\rangle and N′⊒M′N' \sqsupseteq M'. By preservation of well-formedness and coherence (theorems 3.4 and 6.2), theorem O.2 gives communication safety of M′M' at K′K' and non-empty branch lists throughout M′M'. By theorem O.1, N′N' is communication safe at K′K'.

Deadlock Freedom

A deadlock occurs when a network reaches a configuration with no outgoing transition before it terminates. We establish deadlock freedom for networks projected from well-formed, coherent choreographies. After any sequence of transitions from such a projection, the reached configuration can take another step unless its network is the terminated network 00.

In Nyarlathotep, the progress proof relies on messaging state consistency. In the case of choreographic choice, the messaging state must be consistent with each branch followed by the common continuation. Theorem 8.4 establishes progress for projectable choreographies, and theorem 8.5 uses the correctness of EPP to establish deadlock freedom for their projections.

Theorem 8.4 (Progress of Projectable Choreographies). Given a choreographic configuration ⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle that is well-formed, where C∝CC\propto\mathcal{C} and both CC and C\mathcal{C} are projectable, if C≠0C\ne0, then there exist a choreography C′C', a global store Σ′\Sigma', a messaging state K′K', and a transition label μ\mu such that ⟨C,Σ,K,C⟩→μ⟨C′,Σ′,K′,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\mu} \langle C',\Sigma',K',\mathcal{C}\rangle.

Proof. By induction on the size of CC, strengthening the induction hypothesis to allow a projectable continuation DD with K▹(C▹D)K\mathbin{\triangleright}(C\mathbin{\triangleright}D).

Theorem 8.5 (Deadlock Freedom). Given a choreographic configuration ⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle that is well-formed, where C∝CC\propto\mathcal{C}, ⟦C⟧=⟨N⟩\llbracket C\rrbracket=\langle N\rangle, and ⟦C⟧=⟨P⟩\llbracket\mathcal{C}\rrbracket=\langle\mathcal{P}\rangle, if ⟨N,Σ,K,P⟩→μ∗⟨N′,Σ′,K′,P⟩\langle N,\Sigma,K,\mathcal{P}\rangle\mathrel{\xrightarrow{\mu}^{*}} \langle N',\Sigma',K',\mathcal{P}\rangle and

N′≠0N' \ne0, then there exist a network N′′N'', a global store Σ′′\Sigma'', a messaging state K′′K'', and a transition label μ\mu such that ⟨N′,Σ′,K′,P⟩→μ⟨N′′,Σ′′,K′′,P⟩\langle N', \Sigma', K', \mathcal{P}\rangle\xrightarrow{\mu} \langle N'', \Sigma'', K'', \mathcal{P}\rangle.

Proof. By theorem 7.4, the choreography reaches ⟨C′,Σ′,K′,C⟩\langle C', \Sigma', K', \mathcal{C}\rangle along μ⃗\vec{\mu}, with ⟦C′⟧=⟨M′⟩\llbracket C' \rrbracket= \langle M' \rangle and N′⊒M′N' \sqsupseteq M'. Preservation of well-formedness and coherence (theorems 3.4 and 6.2) applies along this execution. Theorem 8.4 gives a step from ⟨C′,Σ′,K′,C⟩\langle C', \Sigma', K', \mathcal{C}\rangle. By theorem 7.1, M′M' can take that step from Σ′\Sigma' and K′K'. By theorem D.3, N′N' can take the same step from Σ′\Sigma' and K′K'.

Related Work

Asynchrony and Nondeterminism in CP. Ozone [25] studies fully out-of-order choreographies. In addition to allowing the sender to continue while a message is pending, Ozone also allows a process waiting for one message to receive another and use it in subsequent computations, provided those actions do not depend on the pending receive. In Nyarlathotep, messages from a given sender to a given receiver are received in FIFO order. However, we are able to encode Ozone’s asynchronous receive feature with choreographic choice by writing a branch for each desired schedule [25]. Ozone does not support choreographic choice, which can express behaviours outside Ozone, such as binding messages to different variables depending on their arrival order. The authors implement their approach as a library for Choral [Giallorenzo et al. 2024], while we mechanise Nyarlathotep in Lean 4.

In Minimal Choreographies, Cruz-Filipe and Montesi [ [11] give separate rules for sending and receiving and prove operational correspondence with networks that use FIFO queues. Kalas [26] also supports asynchronous communication. Its choreographic semantics allows a sender to proceed before its message is received, as in Carbone and Montesi [ [6]. For knowledge of choice, EPP in Kalas uses initial Boolean selections to combine alternatives at the top level. Nyarlathotep adopts Mech’s algebraic approach to full merge. Although these theories do not model choreographic nondeterminism, their studies of asynchrony are inspiring.

For theories that model choreographic nondeterminism, the textbook [22] outlines choreographic choice and asynchronous communication as separate extensions. Mech [27] gives the first correct semantics for choreographic choice with synchronous communication and proves the correctness of EPP. As discussed in § 5, a single communication in Mech can resolve choices at both endpoints. In Nyarlathotep, the send and receive occur in separate transitions, and each can resolve choices at its active process.

Asynchrony and Mixed Choice in MPST. Multiparty session types (MPST) use a global type to describe communication in a protocol and project that type to a local type for each participant. In the original theory of asynchronous MPST [16, 17], a designated sender selects a branch by sending a label to a designated receiver. In the asynchronous system of Castagna et al. [ [7], an external choice can offer receives from different senders. Each local choice contains only inputs or only outputs. Zooid [8] mechanises asynchronous MPST in Rocq and proves trace equivalence between global types and systems of projected local types.

Peters and Yoshida [ [24] study mixed choice in synchronous multiparty sessions. A single choice can contain both sends and receives, possibly involving different peers. A matching send and receive resolve the choices at both endpoints in one synchronised transition. They show that separate choices across peers already express the MM synchronisation pattern and that mixed choices across peers also express the star pattern [23, 33].

Barbanera and Dezani-Ciancaglini [ [1] adapt the mixed choice calculus of Peters and Yoshida [ [24] to asynchronous communication. They type sessions directly against global types and prove subject reduction and session fidelity. Bocchi et al. [ [4] propose an asymmetric mixed choice for asynchronous MPST. Other participants can act in the left branch before a designated observer commits by receiving on the left or sending on the right. The runtime can purge stale messages from the abandoned branch. They prove weak operational correspondence for endpoint projection, treating choice instantiation and stale message purging as silent steps, highlighting the challenges of combining asynchronous communication with protocol-level nondeterminism.

From Mechanised Theory to Certified Compilation for CP. Including aforementioned Kalas and Mech, several studies have explored building certified compiler frameworks for CP with existing mechanised theories. Kalas formalises its theory in HOL4 and passes translated endpoint programs to the verified CakeML compiler, which generates executable machine code. Cruz-Filipe et al. [ [12] study endpoint projection for Core Choreographies, a language with synchronous communication, binary label selections, conditionals, and tail recursion. They mechanise the projection to Stateful Processes in Rocq and prove operational correspondence up to pruning. Cruz-Filipe et al. [ [10] extract this projection to Haskell and use it in hacc, which generates one executable Jolie service per projected process. The certification covers endpoint projection, with the Haskell wrapper and Jolie code generator left to manual inspection. As discussed in § 1, Pirouette [15] and λQC\lambda_{\mathrm{QC}} [28] are both well-known higher-order functional choreographic languages, mechanised in Rocq. However, they can express very limited concurrency features since they both support synchronous communication and require global synchronisation, even for non-involved processes, at every choreography call. Nyarlathotep supports asynchronous communication and choreographic choice and allows processes to enter procedure calls independently. Its mechanised EPP correctness certifies the translation from choreographies to networks. We plan to use Nyarlathotep as an intermediate language in a future certified CP compilation framework. Closure conversion [19] offers a possible starting point for compiling higher-order fragments of Pirouette and λQC\lambda_{\mathrm{QC}} into Mech.

Conclusion and Future Work

We have presented Nyarlathotep, a new CP framework that combines asynchronous communication and choreographic nondeterminism. It supports general branching, out-of-order execution, and general recursion with independent process entry. We proved the correctness of EPP and established communication safety and deadlock freedom. We mechanised the entire theory in Lean 4. The locality property of Nyarlathotep’s semantics enables compositional reasoning and gives the proofs a clearer structure. This is reflected in the size of the Lean 4 mechanisations, with only around 20,000 lines of code for Nyarlathotep and around 40,000 for Mech, which supports fewer features.

As discussed in § 9, researchers have investigated developing certified compilation frameworks for CP based on existing mechanised theories. More recently, researchers also starting building domain-specific languages for stateful processes and implementing security protocols in distributed systems in Lean 4 with its rich metaprogramming features in CSLib [2]. Therefore, we plan to further investigate how to build certified and semi-certified compiler that connect the rich theories of CP to mainstream tooling. We expect Nyarlathotep to serve as an intermediate language for such a framework. Nyarlathotep’s local language agnostic design gives us flexibility in choosing target languages for code generation.

AI Use

The authors have used Codex (models Sol 6.1 and Astra 6) for facilitating the mechanisation. Our uses include proof refactoring and optimisation (reducing heartbeats), proof search, and creating documentation for proofs. AI has not been involved in designing any theory presented in the work or defined/declared in the Lean 4 mechanisation.

Data-Availability Statement

The source code for the complete mechanisation of our theory in the Lean 4 proof assistant is included in the supplementary material accompanying this submission, in the folder “nyarlathotep”. Build instructions and a detailed explanation of the correspondence between the paper formalisation and the mechanisation are provided in the file “README.md”. We intend to submit this artifact for Artifact Evaluation.

References

Process Names

Definition A.1 (Process Names in Choreographies and Instructions).

pn⁡(0)≜∅pn⁡(I ; C)≜pn⁡(I)∪pn⁡(C)pn⁡(p.x:=e)≜{p}pn⁡(p.e→q.x)≜{p,q}pn⁡(p→q[l])≜{p,q}pn⁡(p∼q.x)≜{q}pn⁡(p∼q[l])≜{q}pn⁡(if p.e then C1 else C2)≜{p}∪pn⁡(C1)∪pn⁡(C2)pn⁡(C1+pC2)≜{p}∪pn⁡(C1)∪pn⁡(C2)pn⁡(X(p⃗))≜{p⃗}pn⁡(q:X(p⃗).C)≜{q}\begin{aligned} \operatorname{pn}(0) &\triangleq\varnothing& \operatorname{pn}(I\,;\,C) &\triangleq\operatorname{pn}(I)\cup\operatorname{pn}(C) & \operatorname{pn}(p.x := e) &\triangleq\{p\}\\ \operatorname{pn}(p.e\to q.x) &\triangleq\{p,q\} & \operatorname{pn}(p\to q[l]) &\triangleq\{p,q\} & \operatorname{pn}(p\mathord{\sim}q.x) &\triangleq\{q\}\\ \operatorname{pn}(p\mathord{\sim}q[l]) &\triangleq\{q\} & \operatorname{pn}(\text{if }p.e\text{ then }C_1\text{ else }C_2) &\triangleq\{p\}\cup\operatorname{pn}(C_1)\cup\operatorname{pn}(C_2) & \operatorname{pn}(C_1+_p C_2) &\triangleq\{p\}\cup\operatorname{pn}(C_1)\cup\operatorname{pn}(C_2)\\ \operatorname{pn}(X(\vec{p})) &\triangleq\{\vec{p}\} & \operatorname{pn}(q:X(\vec{p}).C) &\triangleq\{q\} \end{aligned}

Definition A.2 (Process Names in Transition Labels).

pn⁡(skip⁡@p)≜{p}pn⁡(assign⁡@p)≜{p}pn⁡(call⁡@p)≜{p}pn⁡(p.v→q!)≜{p}pn⁡(p.v→q?)≜{q}pn⁡(p→q[l]!)≜{p}pn⁡(p→q[l]?)≜{q}pn⁡(then⁡@p)≜{p}pn⁡(else⁡@p)≜{p}pn⁡(left⁡@p::μ)≜{p}∪pn⁡(μ)pn⁡(right⁡@p::μ)≜{p}∪pn⁡(μ)\begin{aligned} \operatorname{pn}(\operatorname{skip}@p)&\triangleq\{p\} & \operatorname{pn}(\operatorname{assign}@p)&\triangleq\{p\} & \operatorname{pn}(\operatorname{call}@p)&\triangleq\{p\}\\ \operatorname{pn}(p.v\to q!)&\triangleq\{p\} & \operatorname{pn}(p.v\to q?)&\triangleq\{q\} & \operatorname{pn}(p\to q[l]!)&\triangleq\{p\} & \operatorname{pn}(p\to q[l]?)&\triangleq\{q\}\\ \operatorname{pn}(\operatorname{then}@p)&\triangleq\{p\} & \operatorname{pn}(\operatorname{else}@p)&\triangleq\{p\}\\ \operatorname{pn}(\operatorname{left}@p::\mu)&\triangleq\{p\}\cup\operatorname{pn}(\mu) & \operatorname{pn}(\operatorname{right}@p::\mu)&\triangleq\{p\}\cup\operatorname{pn}(\mu) \end{aligned}

Stores and Process Name Substitutions

Definition B.1 (Update Operations for Stores).

σ[y↦v](x)≜{vif x=yσ(x)otherwiseΣ[q.x↦v](p)≜{Σ(p)[x↦v]if p=qΣ(p)otherwise\sigma[y\mapsto v](x)\triangleq \begin{cases} v & \text{if }x=y\\ \sigma(x) & \text{otherwise} \end{cases} \qquad \Sigma[q.x\mapsto v](p)\triangleq \begin{cases} \Sigma(p)[x\mapsto v] & \text{if }p=q\\ \Sigma(p) & \text{otherwise} \end{cases}

Definition B.2 (Name Substitution for Process Names and Sequences of Process Names).

p[r/s]≜{rif p=spotherwise(p1,…,pn)[r/s]≜(p1[r/s],…,pn[r/s])p[r/s]\triangleq \begin{cases} r & \text{if }p=s\\ p & \text{otherwise} \end{cases} \qquad (p_1,\ldots,p_n)[r/s]\triangleq(p_1[r/s],\ldots,p_n[r/s])

Definition B.3 (Name Substitution for Choreographies and Instructions).

0[r/s]≜0(p.x:=e)[r/s]≜(p[r/s]).x:=e(q:X(p⃗).C)[r/s]≜q[r/s]:X(p⃗[r/s]).(C[r/s])(p.e→q.x)[r/s]≜(p[r/s]).e→(q[r/s]).x(p∼q.x)[r/s]≜(p[r/s]).e∼(q[r/s]).x(I ; C)[r/s]≜(I[r/s]) ; (C[r/s])(X(p⃗))[r/s]≜X(p⃗[r/s])(C1+pC2)[r/s]≜(C1[r/s])+p[r/s](C2[r/s])(p→q[l])[r/s]≜(p[r/s])→(q[r/s])[l](p∼q[l])[r/s]≜(p[r/s])∼(q[r/s])[l](if p.e then C1 else C2)[r/s]≜if (p[r/s]).e then (C1[r/s]) else (C2[r/s])C[r1,…,rn/s1,…,sn]≜C[r1/s1]…[rn/sn]\begin{aligned} 0[r/s]&\triangleq0\\ (p.x:=e)[r/s]&\triangleq(p[r/s]).x:=e\\ (q:X(\vec{p}).C)[r/s]&\triangleq q[r/s]:X(\vec{p}[r/s]).(C[r/s])\\ (p.e\to q.x)[r/s]&\triangleq(p[r/s]).e\to(q[r/s]).x\\ (p\mathord{\sim}q.x)[r/s]&\triangleq(p[r/s]).e\mathord{\sim}(q[r/s]).x\\ (I\,;\,C)[r/s]&\triangleq(I[r/s])\,;\,(C[r/s])\\ (X(\vec{p}))[r/s]&\triangleq X(\vec{p}[r/s])\\ (C_1+_p C_2)[r/s]&\triangleq(C_1[r/s])+_{p[r/s]}(C_2[r/s])\\ (p\to q[l])[r/s]&\triangleq(p[r/s])\to(q[r/s])[l]\\ (p\mathord{\sim}q[l])[r/s]&\triangleq(p[r/s])\mathord{\sim}(q[r/s])[l]\\ (\text{if }p.e\text{ then }C_1\text{ else }C_2)[r/s]&\triangleq\text{if }(p[r/s]).e\text{ then }(C_1[r/s])\text{ else }(C_2[r/s])\\ C[r_1,\ldots,r_n/s_1,\ldots,s_n]&\triangleq C[r_1/s_1]\ldots[r_n/s_n] \end{aligned}

Definition B.4 (Name Substitution for Process Terms and Instructions).

0[r/s]≜0(p&{li:Pi}i∈I)[r/s]≜p&{li:Pi}i∈I[r/s](I ; P)[r/s]≜(I[r/s]) ; (P[r/s])(p!e)[r/s]≜p[r/s]!e(p⊕l)[r/s]≜p[r/s]⊕l(x:=e)[r/s]≜x:=e(p?x)[r/s]≜p[r/s]?x(X(p⃗))[r/s]≜X(p⃗[r/s])(if e then P1 else P2)[r/s]≜if e then (P1[r/s]) else (P2[r/s])(P1+P2)[r/s]≜(P1[r/s])+(P2[r/s])P[r1,…,rn/s1,…,sn]≜P[r1/s1]…[rn/sn]\begin{aligned} 0[r/s]&\triangleq0\\ (p\mathbin{\&}\{l_i:P_i\}_{i\in I})[r/s]&\triangleq p\mathbin{\&}\{l_i:P_i\}_{i\in I}[r/s] & (I\,;\,P)[r/s]&\triangleq(I[r/s])\,;\,(P[r/s])\\ (p!e)[r/s]&\triangleq p[r/s]!e & (p\oplus l)[r/s]&\triangleq p[r/s]\oplus l\\ (x:=e)[r/s]&\triangleq x:=e & (p?x)[r/s]&\triangleq p[r/s]?x\\ (X(\vec{p}))[r/s]&\triangleq X(\vec{p}[r/s])\\ (\text{if }e\text{ then }P_1\text{ else }P_2)[r/s]&\triangleq\text{if }e\text{ then }(P_1[r/s])\text{ else }(P_2[r/s])\\ (P_1+P_2)[r/s]&\triangleq(P_1[r/s])+(P_2[r/s])\\ P[r_1,\ldots,r_n/s_1,\ldots,s_n]&\triangleq P[r_1/s_1]\ldots[r_n/s_n] \end{aligned}

Well-formedness of Choreographies

We define the well-formedness of choreographies with the notation ⟨C,{r⃗},C⟩✓\langle\mathcal{C}, \{\vec{r}\}, C\rangle\checkmark. It denotes that a choreography CC is well-formed under a set of choreographic procedures C\mathcal{C} and a set {r⃗}\{\vec{r}\} of processes that may be involved. Figure 17 gives the formal definition of well-formed choreographies.

Well-formedness rules for choreographies

Figure 17. Well-Formedness of Choreographies

Merge and the Branching Order

We take an algebraic approach for defining the merge operation ⊔\sqcup, forming join-semilattice structures (Process?,⊔)(\mathrm{Process?}, \sqcup) and (PInstr?,⊔)(\mathrm{PInstr?}, \sqcup). The type signatures of (⊔)(\sqcup) are:

⊔:Process?→Process?→Process?⊔:PInstr?→PInstr?→PInstr?\sqcup: \mathrm{Process?} \to\mathrm{Process?} \to\mathrm{Process?} \qquad\sqcup: \mathrm{PInstr?} \to\mathrm{PInstr?} \to\mathrm{PInstr?}

We formally define (⊔)(\sqcup) for process terms and instructions in Figure 18a and Figure 18b. Note that P~\tilde{P} is a term of the option type Process?\mathrm{Process?}, i.e., either ⟨P⟩\langle P\rangle or a none term ⟨⟩\langle\rangle, and I~\tilde{I} is a term of PInstr?\mathrm{PInstr?}.

The Merge Operation for Process Terms and Process Instructions

Figure 18. The Merge Operation for Process Terms and Process Instructions

With the join-semilattice construction, we derive that (⊒)(\sqsupseteq) is a partial order on Process?\mathrm{Process?} with properties: reflexivity, antisymmetry, and transitivity (cf. proposition F.6). We establish a lax interchange law (cf. proposition D.1) connecting merge (⊔)(\sqcup) and sequential composition (∘)(\circ) under (⊒)(\sqsupseteq). We lift (∘)(\circ) to Process?\mathrm{Process?}, returning ⟨P∘Q⟩\langle P \circ Q\rangle for ⟨P⟩\langle P\rangle and ⟨Q⟩\langle Q\rangle, and ⟨⟩\langle\rangle if either argument is ⟨⟩\langle\rangle.

Proposition D.1 (Lax Interchange Law). For any terms P~1\tilde{P}_1, P~2\tilde{P}_2, Q~1\tilde{Q}_1, and Q~2\tilde{Q}_2 in the set Process?\mathrm{Process?}, the following relation holds:

(P~1⊔P~2)∘(Q~1⊔Q~2)⊒(P~1∘Q~1)⊔(P~2∘Q~2)(\tilde{P}_1 \sqcup\tilde{P}_2) \circ(\tilde{Q}_1 \sqcup\tilde{Q}_2) \sqsupseteq(\tilde{P}_1 \circ\tilde{Q}_1) \sqcup(\tilde{P}_2 \circ\tilde{Q}_2)

In theorem D.2, we define the more branches relation on networks by lifting the relation on Process?\mathrm{Process?} pointwise to Net\mathrm{Net}.

Definition D.2 (⊒\sqsupseteq on Net). For any NN and MM in Net\mathrm{Net}, N⊒MN \sqsupseteq M iff for any process pp, ⟨N(p)⟩⊒⟨M(p)⟩\langle N(p)\rangle\sqsupseteq\langle M(p)\rangle.

We show that the relation (⊒)(\sqsupseteq) is a simulation relation, if N⊒MN \sqsupseteq M and the smaller network MM performs a transition to M′M', then NN can perform the same transition to some N′N' such that N′⊒M′N' \sqsupseteq M', as formalised in Theorem D.3.

Theorem D.3 (Simulation under ⊒\sqsupseteq). For any networks NN and MM, if N⊒MN \sqsupseteq M and ⟨M,Σ,K,P⟩⟶μ⟨M′,Σ′,K′,P⟩\langle M,\Sigma,K,\mathcal{P}\rangle\mathrel{\longrightarrow^\mu} \langle M',\Sigma',K',\mathcal{P}\rangle, then there exists an N′N' such that ⟨N,Σ,K,P⟩⟶μ⟨N′,Σ′,K′,P⟩\langle N,\Sigma,K,\mathcal{P}\rangle\mathrel{\longrightarrow^\mu} \langle N',\Sigma',K',\mathcal{P}\rangle and N′⊒M′N' \sqsupseteq M'.

Proof. By structural induction on the derivation of the transition. □\square

Coherence

We define coherence between a choreography and choreographic procedure definitions for handling recursion correctly. It ensures the consistency of projection for partially entered procedure calls.

Algebraic Properties of Operators

Proposition F.1 (Sequential Composition of Choreographies Forms a Monoid).

0∘C=CC∘0=C(Identity element)0 \circ C = C \qquad C \circ0 = C \qquad\text{(Identity element)}
(C1∘C2)∘C3=C1∘(C2∘C3)(Associativity)(C_1 \circ C_2) \circ C_3 = C_1 \circ(C_2 \circ C_3) \qquad\text{(Associativity)}

Proof. By structural induction on the choreography.

Proposition F.2 (Parallel Composition of Networks Forms a Monoid).

0∣N=NN∣0=N(Identity element)0 \mid N = N \qquad N \mid0 = N \qquad\text{(Identity element)}
N1∣(N2∣N3)=(N1∣N2)∣N3(Associativity)N_1 \mid(N_2 \mid N_3) = (N_1 \mid N_2) \mid N_3 \qquad\text{(Associativity)}

Proof. By unfolding the definition of parallel composition and applying function extensionality.

Proposition F.3 (Sequential Composition of Process Terms Forms a Monoid).

0∘P=PP∘0=P(Identity element)0 \circ P = P \qquad P \circ0 = P \qquad\text{(Identity element)}
(P1∘P2)∘P3=P1∘(P2∘P3)(Associativity)(P_1 \circ P_2) \circ P_3 = P_1 \circ(P_2 \circ P_3) \qquad\text{(Associativity)}

Proof. By structural induction on the process term.

Proposition F.4 (Sequential Composition of Networks Forms a Monoid).

0∘N=NN∘0=N(Identity element)0 \circ N = N \qquad N \circ0 = N \qquad\text{(Identity element)}
(N1∘N2)∘N3=N1∘(N2∘N3)(Associativity)(N_1 \circ N_2) \circ N_3 = N_1 \circ(N_2 \circ N_3) \qquad\text{(Associativity)}

Proof. By pointwise lifting from proposition F.3.

Proposition F.5 (Join-Semilattice Properties of (Process?, ⊔\sqcup)).

P~⊔P~=P~(Idempotency)\widetilde{P} \sqcup\widetilde{P} = \widetilde{P} \qquad\text{(Idempotency)}
P~⊔Q~=Q~⊔P~(Commutativity)\widetilde{P} \sqcup\widetilde{Q} = \widetilde{Q} \sqcup\widetilde{P} \qquad\text{(Commutativity)}
(P~⊔Q~)⊔R~=P~⊔(Q~⊔R~)(Associativity)(\widetilde{P} \sqcup\widetilde{Q}) \sqcup\widetilde{R} = \widetilde{P} \sqcup(\widetilde{Q} \sqcup\widetilde{R}) \qquad\text{(Associativity)}

Proof. By structural induction on the process term.

Proposition F.6 (The Relation ⪰\succeq is a Partial Order).

P~⪰P~(Reflexivity)\widetilde{P} \succeq\widetilde{P} \qquad\text{(Reflexivity)}
P~⪰Q~∧Q~⪰P~⇒P~=Q~(Antisymmetry)\widetilde{P} \succeq\widetilde{Q} \land\widetilde{Q} \succeq\widetilde{P} \Rightarrow\widetilde{P} = \widetilde{Q} \qquad\text{(Antisymmetry)}
P~⪰Q~∧Q~⪰R~⇒P~⪰R~(Transitivity)\widetilde{P} \succeq\widetilde{Q} \land\widetilde{Q} \succeq\widetilde{R} \Rightarrow\widetilde{P} \succeq\widetilde{R} \qquad\text{(Transitivity)}

Proof. By the definition of the relation ⪰\succeq and join-semilattice properties of (Process?, ⊔\sqcup).

Proposition F.7 (Sequential Composition of Processes Distributes over Merge).

P~∘(Q~⊔R~)=(P~∘Q~)⊔(P~∘R~)(Left Distributivity)\widetilde{P} \circ(\widetilde{Q} \sqcup\widetilde{R}) = (\widetilde{P} \circ\widetilde{Q}) \sqcup(\widetilde{P} \circ\widetilde{R}) \qquad\text{(Left Distributivity)}
(P~⊔Q~)∘R~=(P~∘R~)⊔(Q~∘R~)(Right Distributivity)(\widetilde{P} \sqcup\widetilde{Q}) \circ\widetilde{R} = (\widetilde{P} \circ\widetilde{R}) \sqcup(\widetilde{Q} \circ\widetilde{R}) \qquad\text{(Right Distributivity)}

Proof. By structural induction on the process term.

Localised Process Language Semantics

Because the asynchronous model does not require communication synchronisation, we can define a localised semantics for the process language. A transition by an active process has the form ⟨P,Σ,K,P⟩→μp⟨P′,Σ′,K′,P⟩\langle P, \Sigma, K, \mathcal{P}\rangle\xrightarrow{\mu}_{p} \langle P', \Sigma', K', \mathcal{P}\rangle, where ⟨P,Σ,K,P⟩\langle P, \Sigma, K, \mathcal{P}\rangle is a process language configuration. Formally, we define the localised semantics in Figure 20.

Localised semantics for the process language

Figure 20. Localised Semantics for the Process Language in Nyarlathotep

Lemma G.1 (Local Transitions of Atomic Networks). Given a process name pp and a transition label μ\mu, if ⟨P,Σ,K,P⟩→μp⟨P′,Σ′,K′,P⟩\langle P, \Sigma, K, \mathcal{P}\rangle\xrightarrow{\mu}_{p} \langle P', \Sigma', K', \mathcal{P}\rangle, then ⟨p[P],Σ,K,P⟩→μ⟨p[P′],Σ′,K′,P⟩\langle p[P], \Sigma, K, \mathcal{P}\rangle\xrightarrow{\mu} \langle p[P'], \Sigma', K', \mathcal{P}\rangle.

Lemma G.2 (Lifting Local Transitions to Networks). Given networks NN and N′N', a process name pp, and a transition label μ\mu, if N(q)=N′(q)N(q) = N'(q) for every q≠pq \ne p and ⟨N(p),Σ,K,P⟩→μp⟨N′(p),Σ′,K′,P⟩\langle N(p), \Sigma, K, \mathcal{P} \rangle\xrightarrow{\mu}_{p} \langle N'(p), \Sigma', K', \mathcal{P} \rangle, then ⟨N,Σ,K,P⟩→μ⟨N′,Σ′,K′,P⟩\langle N, \Sigma, K, \mathcal{P} \rangle\xrightarrow{\mu} \langle N', \Sigma', K', \mathcal{P} \rangle.

Lemma G.3 (Localisation of Network Transitions). For a network configuration ⟨N,Σ,K,P⟩\langle N, \Sigma, K, \mathcal{P} \rangle and a transition label μ\mu, if ⟨N,Σ,K,P⟩→μ⟨N′,Σ′,K′,P⟩\langle N, \Sigma, K, \mathcal{P} \rangle\xrightarrow{\mu} \langle N', \Sigma', K', \mathcal{P} \rangle, then there exists a process name pp such that pn⁡(μ)={p}\operatorname{pn}(\mu) = \{p\} and ⟨N(p),Σ,K,P⟩→μp⟨N′(p),Σ′,K′,P⟩\langle N(p), \Sigma, K, \mathcal{P} \rangle\xrightarrow{\mu}_{p} \langle N'(p), \Sigma', K', \mathcal{P} \rangle.

Localised Transitions for the Messaging State

The transition K→μK′K \xrightarrow{\mu} K' of a messaging state with a transition label μ\mu, defined in Figure 21.

Messaging State Transitions in Nyarlathotep

Figure 21. Messaging State Transitions in Nyarlathotep

K(q,p)=m⃗K→p.v→q!K[(q,p)↦m⃗::v]K(q,p)=v::m⃗K→p.v→q?K[(q,p)↦m⃗]\frac{K(q,p)=\vec{m}}{K \xrightarrow{p.v\to q!} K[(q,p)\mapsto\vec{m}::v]} \qquad \frac{K(q,p)=v::\vec{m}}{K \xrightarrow{p.v\to q?} K[(q,p)\mapsto\vec{m}]}
K(q,p)=m⃗K→p→q[l]!K[(q,p)↦m⃗::l]K(q,p)=l::m⃗K→p→q[l]?K[(q,p)↦m⃗]\frac{K(q,p)=\vec{m}}{K \xrightarrow{p\to q[l]!} K[(q,p)\mapsto\vec{m}::l]} \qquad \frac{K(q,p)=l::\vec{m}}{K \xrightarrow{p\to q[l]?} K[(q,p)\mapsto\vec{m}]}
K→assign⁡@pKK→then⁡@pKK→else⁡@pKK→call⁡@pK\frac{}{K \xrightarrow{\operatorname{assign}@p} K} \qquad \frac{}{K \xrightarrow{\operatorname{then}@p} K} \qquad \frac{}{K \xrightarrow{\operatorname{else}@p} K} \qquad \frac{}{K \xrightarrow{\operatorname{call}@p} K}
K→skip⁡@pKK→μK′K→left⁡@p::μK′K→μK′K→right⁡@p::μK′\frac{}{K \xrightarrow{\operatorname{skip}@p} K} \qquad \frac{K \xrightarrow{\mu} K'}{K \xrightarrow{\operatorname{left}@p::\mu} K'} \qquad \frac{K \xrightarrow{\mu} K'}{K \xrightarrow{\operatorname{right}@p::\mu} K'}

Lemma H.1 (Removal of a Queue Head at an Uninvolved Receiver). Given a messaging state transition K→μK′K \xrightarrow{\mu} K' and process names pp and qq, if q∉pn⁡(μ)q \notin\operatorname{pn}(\mu) and K(q,p)=m::m⃗K(q,p)=m::\vec{m}, then there exists a queue m⃗′\vec{m}' such that K′(q,p)=m::m⃗′K'(q,p)=m::\vec{m}' and K[(q,p)↦m⃗]→μK′[(q,p)↦m⃗′]K[(q,p)\mapsto\vec{m}] \xrightarrow{\mu} K'[(q,p)\mapsto\vec{m}'].

Proof. By structural induction on the derivation of K→μK′K \xrightarrow{\mu} K'. □

Lemma H.2 (Isolating Messaging State Transitions). If ⟨N,Σ,K,P⟩→μ⟨N′,Σ′,K′,P⟩\langle N, \Sigma, K, \mathcal{P} \rangle\xrightarrow{\mu} \langle N', \Sigma', K', \mathcal{P} \rangle, then K→μK′K \xrightarrow{\mu} K'.

Proof. By structural induction on the derivation of the network transition. □

Lemma H.3 (Replacement of Messaging States in Choreographic Transitions). Given a choreographic transition ⟨C,Σ,K,C⟩→μ⟨C′,Σ′,K′,C⟩\langle C, \Sigma, K, \mathcal{C} \rangle\xrightarrow{\mu} \langle C', \Sigma', K', \mathcal{C} \rangle and a messaging state transition K0→μK0′K_0 \xrightarrow{\mu} K'_0, the choreography can perform ⟨C,Σ,K0,C⟩→μ⟨C′,Σ′,K0′,C⟩\langle C, \Sigma, K_0, \mathcal{C} \rangle\xrightarrow{\mu} \langle C', \Sigma', K'_0, \mathcal{C} \rangle.

Proof. By structural induction on the derivation of the choreographic transition. □

Finite Functions and Finite Networks

Finite Function

In our formalisation, a finite function is a function with finite support. We write it as f^:A→fB\hat{f}: A \to_f B. For mechanisation, Mathlib [31] provides a corresponding structure Finsupp, but some of its operations are noncomputable to avoid decidability requirements. To support computation, we introduce FinFun, pairing a function f:A→Bf:A \to B with a proof of finite support, together with APIs that preserve this invariant. Both FinFun and its APIs are included in CSLib, the Lean Computer Science Library.

Definition I.1 (Lifting Binary Operations to Finite Functions). Given a binary operation ⊙\odot defined on the set BB, we lift ⊙\odot to finite functions f^\hat{f} and g^\hat{g} of the type A→fBA \to_f B.

mapBin⁡ f^ g^ ⊙≔{⟨a↦ba⟩if supp⁡(f^)=supp⁡(g^) and for each a∈supp⁡(f^), f^(a)⊙g^(a)=⟨ba⟩⟨⟩otherwise\operatorname{mapBin}\ \hat{f}\ \hat{g}\ \odot\coloneqq \begin{cases} \langle a \mapsto b_a\rangle& \text{if }\operatorname{supp}(\hat{f})=\operatorname{supp}(\hat{g})\text{ and for each }a\in\operatorname{supp}(\hat{f}),\ \hat{f}(a)\odot\hat{g}(a)=\langle b_a\rangle\\ \langle\rangle& \text{otherwise} \end{cases}

Using mapBin⁡\operatorname{mapBin}, we define the merge operation for finite networks:

N^⊔M^≔mapBin⁡ N^ M^ ⊔,\hat{N}\sqcup\hat{M}\coloneqq\operatorname{mapBin}\ \hat{N}\ \hat{M}\ \sqcup,

where (⊔)(\sqcup) on the right-hand side is the merge operation on Process?.

Finite Network

EPP produces networks of finite support. Definition I.2 shows such a finite network (N^\hat{N}).

Definition I.2 (Finite Network). A finite network N^\hat{N} is a finite function (introduced in section 2.3) from process names to process terms, i.e., N^:PName→fProcess\hat{N}:\mathrm{PName}\to_f\mathrm{Process}.

Process Removal and Network Restriction

We have the process removal and the network restriction operations (cf. Figure 22). The process removal operation N∖pN \setminus p updates NN by setting N(p)=0N(p)=0. Process removal is commutative and associative. We can generalise it to finite sets of processes, written as N∖{p⃗}N\setminus\{\vec{p}\}. The network restriction operation is the opposite, which extracts a subnetwork containing only a finite set of processes {p⃗}\{\vec{p}\} from a given network NN. The resulting subnetwork is a finite network written as N↾{p⃗}N\upharpoonright\{\vec{p}\}.

Process removal and network restriction

Figure 22. Process Removal and Network Restriction

:::`

Properties of the Semantics of Choreographies

If a choreography can perform a transition with label μ\mu, then the choreography must contains all the processes in the transition label μ\mu, which is shown in theorem K.1.

Theorem K.1 (Transitions Involve Only Processes in the Choreography). For any choreographic configuration ⟨C,Σ,C⟩\langle C,\Sigma,\mathcal{C}\rangle and transition label μ\mu, if ⟨C,Σ,C⟩→μ⟨C′,Σ′,C′⟩\langle C,\Sigma,\mathcal{C}\rangle\xrightarrow{\mu} \langle C',\Sigma',\mathcal{C}'\rangle, then pn⁡(μ)⊆pn⁡(C)\operatorname{pn}(\mu)\subseteq\operatorname{pn}(C).

Proof. By structural induction on the derivation of the transition. □

A choreographic transition may change the projection onto a process even when that process is not involved in the transition. The following theorem states that the projection onto that process before the transition offers every branch that its projection after the transition offers,

Theorem K.2 (Projection of Uninvolved Processes). Given a well-formed choreographic configuration ⟨C,Σ,C⟩\langle C,\Sigma,\mathcal{C}\rangle, if ⟨C,Σ,C⟩→μ⟨C′,Σ′,C′⟩\langle C,\Sigma,\mathcal{C}\rangle\xrightarrow{\mu} \langle C',\Sigma',\mathcal{C}'\rangle, then for any process p∉pn⁡(μ)p\notin\operatorname{pn}(\mu), ⟦C⟧p⊒⟦C′⟧p\llbracket C\rrbracket_p\sqsupseteq\llbracket C'\rrbracket_p.

Proof. By structural induction on the derivation of the transition ⟨C,Σ,C⟩→μ⟨C′,Σ′,C′⟩\langle C,\Sigma,\mathcal{C}\rangle\xrightarrow{\mu} \langle C',\Sigma',\mathcal{C}'\rangle. □

Properties of the Semantics of Networks

As in the choreographic case, the processes involved in a network transition are exactly those named in its label, shown in theorem L.1.

Theorem L.1 (Transitions Involve Only Running Processes). For any network configuration ⟨N,Σ,P⟩\langle N,\Sigma,\mathcal{P}\rangle and transition label μ\mu, if ⟨N,Σ,P⟩→μ⟨N′,Σ′,P⟩\langle N,\Sigma,\mathcal{P}\rangle\xrightarrow{\mu} \langle N',\Sigma',\mathcal{P}\rangle, then pn⁡(μ)⊆supp⁡(N)\operatorname{pn}(\mu) \subseteq\operatorname{supp}(N).

Proof. By structural induction on the derivation of the transition. □

Based on this property, we establish two further properties of network transitions involving network restriction and process removal. If a network can perform a transition, then its subnetwork containing only the processes named in the transition label can perform the same transition, shown in theorem L.2.

Theorem L.2 (Restriction to Involved Processes Preserves Transitions). For any network configuration ⟨N,Σ,P⟩\langle N,\Sigma,\mathcal{P}\rangle and transition label μ\mu, if ⟨N,Σ,P⟩→μ⟨N′,Σ′,P⟩\langle N,\Sigma,\mathcal{P}\rangle\xrightarrow{\mu} \langle N',\Sigma',\mathcal{P}\rangle, then ⟨N↾pn⁡(μ),Σ,P⟩→μ⟨N′↾pn⁡(μ),Σ′,P⟩\langle N\mathbin{\upharpoonright}\operatorname{pn}(\mu),\Sigma,\mathcal{P}\rangle\xrightarrow{\mu} \langle N'\mathbin{\upharpoonright}\operatorname{pn}(\mu),\Sigma',\mathcal{P}\rangle.

Proof. By structural induction on the derivation of the transition. □

Similarly, removing processes that the transition label does not mention preserves the transition, shown in theorem L.3.

Theorem L.3 (Removal of Uninvolved Processes Preserves Transitions). For any network configuration ⟨N,Σ,P⟩\langle N,\Sigma,\mathcal{P}\rangle and transition label μ\mu, if ⟨N,Σ,P⟩→μ⟨N′,Σ′,P⟩\langle N,\Sigma,\mathcal{P}\rangle\xrightarrow{\mu} \langle N',\Sigma',\mathcal{P}\rangle, then for any finite set of processes such that {p⃗}#pn⁡(μ)\{\vec{p}\} \mathbin{\#} \operatorname{pn}(\mu), ⟨N∖{p⃗},Σ,P⟩→μ⟨N′∖{p⃗},Σ′,P⟩\langle N\setminus\{\vec{p}\},\Sigma,\mathcal{P}\rangle\xrightarrow{\mu} \langle N'\setminus\{\vec{p}\},\Sigma',\mathcal{P}\rangle.

Proof. By structural induction on the derivation of the transition. □

Theorem L.4 (Lax Compatibility of Merge at the Active Process). For any process terms PP, QQ, P′P', and Q′Q' such that every receive-branch list in PP and QQ is strictly ordered by label and ⟨P⟩⊔⟨Q⟩=⟨R⟩\langle P\rangle\mathbin{\sqcup} \langle Q\rangle= \langle R\rangle, if ⟨P,Σ,K,P⟩→μp⟨P′,Σ1′,K1′,P⟩\langle P,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\mu}_{p} \langle P',\Sigma'_1,K'_1,\mathcal{P}\rangle and ⟨Q,Σ,K,P⟩→μp⟨Q′,Σ2′,K2′,P⟩\langle Q,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\mu}_{p} \langle Q',\Sigma'_2,K'_2,\mathcal{P}\rangle, then there exists a process term SS such that ⟨R,Σ,K,P⟩→μp⟨S,Σ1′,K1′,P⟩\langle R,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\mu}_{p} \langle S,\Sigma'_1,K'_1,\mathcal{P}\rangle and ⟨S⟩⊒⟨⟨P′⟩⊔⟨Q′⟩⟩\langle S\rangle\sqsupseteq\langle\langle P'\rangle\mathbin{\sqcup} \langle Q'\rangle\rangle.

Proof. By induction on the local transition derivation for PP, using proposition D.1 when reattaching continuations. □

Coherence

We present the formal definition of coherence between choreographies and their corresponding sets of choreographic procedures in Figure 19.

Coherence of Choreographies

Figure 19. Coherence of Choreographies

Multi-step Transitions for Choreographies and Networks

The formal definitions of multi-step transitions for both choreographies and networks are shown in Figure 23a and Figure 23b, respectively. Both multi-step transition relations have two rules. The rule REFL allows any configuration to take a multi-step transition to itself with an empty transition label. The rule STEP-L states that if a configuration takes a single-step transition to a second configuration with label μ\mu, and the second configuration takes a multi-step transition to a third configuration with label μ⃗\vec{\mu}, then the first configuration can take a multi-step transition to the third configuration with a label obtained by prepending μ\mu to μ⃗\vec{\mu}. In our Lean 4 mechanisation, we instantiate CSLib’s multi-step transition relation MTr for choreographies and networks.

Multi-step transition rules for choreographies and networks

Figure 23. Multi-Step Transitions

⟨C,Σ,K,C⟩→ε⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\varepsilon} \langle C,\Sigma,K,\mathcal{C}\rangle
⟨C,Σ,K,C⟩→μ⟨C′,Σ′,K′,C⟩⟨C′,Σ′,K′,C⟩→μ⃗⟨C′′,Σ′′,K′′,C⟩⟨C,Σ,K,C⟩→μ::μ⃗⟨C′′,Σ′′,K′′,C⟩\frac{\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\mu} \langle C',\Sigma',K',\mathcal{C}\rangle\qquad\langle C',\Sigma',K',\mathcal{C}\rangle\xrightarrow{\vec{\mu}} \langle C'',\Sigma'',K'',\mathcal{C}\rangle}{\langle C,\Sigma,K,\mathcal{C}\rangle\xrightarrow{\mu::\vec{\mu}} \langle C'',\Sigma'',K'',\mathcal{C}\rangle}

(a) Multi-Step Transitions for Choreographies

⟨N,Σ,K,P⟩→ε⟨N,Σ,K,P⟩\langle N,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\varepsilon} \langle N,\Sigma,K,\mathcal{P}\rangle
⟨N,Σ,K,P⟩→μ⟨N′,Σ′,K′,P⟩⟨N′,Σ′,K′,P⟩→μ⃗⟨N′′,Σ′′,K′′,P⟩⟨N,Σ,K,P⟩→μ::μ⃗⟨N′′,Σ′′,K′′,P⟩\frac{\langle N,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\mu} \langle N',\Sigma',K',\mathcal{P}\rangle\qquad\langle N',\Sigma',K',\mathcal{P}\rangle\xrightarrow{\vec{\mu}} \langle N'',\Sigma'',K'',\mathcal{P}\rangle}{\langle N,\Sigma,K,\mathcal{P}\rangle\xrightarrow{\mu::\vec{\mu}} \langle N'',\Sigma'',K'',\mathcal{P}\rangle}

(b) Multi-Step Transitions for Networks

O EPP Produces Communication Safe States

Lemma O.1 (Communication Safety with More Branches). If MM is communication safe at KK, then NN is communication safe at KK.

Proof. By case analysis on process merge. □

Theorem O.2 (EPP Produces Communication-Safe States). If ⟨C,Σ,K,C⟩\langle C,\Sigma,K,\mathcal{C}\rangle is well-formed, C∝CC \propto\mathcal{C}, and ⟦C⟧=⟨N⟩\llbracket C\rrbracket= \langle N\rangle, then NN is communication safe at KK.

Proof. By induction on CC. □

References

  1. [1]Franco Barbanera and Mariangiola Dezani-Ciancaglini. 2026. Asynchronous Multiparty Sessions with Mixed Choice. Electronic Proceedings in Theoretical Computer Science 444 (April 2026), 11–22. doi:10.4204/EPTCS.444.2
  2. [2]Clark Barrett, Swarat Chaudhuri, Fabrizio Montesi, Jimi Grundy, Pushmeet Kohli, Leonardo de Moura, Alexandre Rademaker, and Sorrachai Yingchareonthawonchai. 2026. CSLib: The Lean Computer Science Library. arXiv:2602.04846 [cs.LO] https://arxiv.org/abs/2602.04846
  3. [3]Mako Bates, Shun Kashiwa, Syed Jafri, Gan Shen, Lindsey Kuper, and Joseph P. Near. 2025. Efficient, Portable, Census-Polymorphic Choreographic Programming. Proc. ACM Program. Lang. 9, PLDI (2025), 1143–1166. doi:10.1145/3729296DOI
  4. [4]Laura Bocchi, Raymond Hu, Adriana Laura Voinea, and Simon Thompson. 2026. Mixed Choice in Asynchronous Multiparty Session Types. Proceedings of the ACM on Programming Languages 10, OOPSLA1 (April 2026), 1542–1569. doi:10.1145/3798256DOI
  5. [5]Mario Bravetti, Marco Carbone, and Gianluigi Zavattaro. 2017. Undecidability of Asynchronous Session Subtyping. Inf. Comput. 256 (2017), 300–320. doi:10.1016/j.ic.2017.07.010DOI
  6. [6]Marco Carbone and Fabrizio Montesi. 2013. Deadlock-freedom-by-design: multiparty asynchronous global programming. In The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’13, Rome, Italy - January 23 - 25, 2013, Roberto Giacobazzi and Radhia Cousot (Eds.). ACM, 263–274. doi:10.1145/2429069.2429101DOI
  7. [7]Giuseppe Castagna, Mariangiola Dezani-Ciancaglini, and Luca Padovani. 2012. On Global Types and Multi-Party Session. Log. Methods Comput. Sci. 8, 1 (2012). doi:10.2168/LMCS-8(1:24)2012DOI
  8. [8]David Castro-Perez, Francisco Ferreira, Lorenzo Gheri, and Nobuko Yoshida. 2021. Zooid: a DSL for certified multiparty computation: from mechanised metatheory to certified multiparty processes. In PLDI ’21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Virtual Event, Canada, June 20-25, 2021, Stephen N. Freund and Eran Yahav (Eds.). ACM, 237–251. doi:10.1145/3453483.3454041
  9. [9]Kaushik Chakraborty. 2025. UniChorn: Unison’s Functional Choreographic Programming library. https://share.unison-lang.org/@kaychakhs/unichorn/.
  10. [10]Luís Cruz-Filipe, Lovro Lugovic, and Fabrizio Montesi. 2023. Certified Compilation of Choreographies with hacc. In Formal Techniques for Distributed Objects, Components, and Systems - 43rd IFIP WG 6.1 International Conference, FORTE 2023, Held as Part of the 18th International Federated Conference on Distributed Computing Techniques, DisCoTec 2023, Lisbon, Portugal, June 19-23, 2023, Proceedings (Lecture Notes in Computer Science, Vol. 13910), Marieke Huisman and António Ravara (Eds.). Springer, 29–36. doi:10.1007/978-3-031-35355-0_3
  11. [11]Luís Cruz-Filipe and Fabrizio Montesi. 2017. On Asynchrony and Choreographies. In Proceedings 10th Interaction and Concurrency Experience, ICE@DisCoTec 2017, Neuchâtel, Switzerland, 21-22nd June 2017 (EPTCS, Vol. 261), Massimo Bartoletti, Laura Bocchi, Ludovic Henrio, and Sophia Knight (Eds.). 76–90. doi:10.4204/EPTCS.261.8
  12. [12]Luís Cruz-Filipe, Fabrizio Montesi, and Marco Peressotti. 2021. Certifying Choreography Compilation. In Theoretical Aspects of Computing - ICTAC 2021 - 18th International Colloquium, Virtual Event, Nur-Sultan, Kazakhstan, September 8-10, 2021, Proceedings (Lecture Notes in Computer Science, Vol. 12819), Antonio Cerone and Peter Csaba Ölveczky (Eds.). Springer, 115–133. doi:10.1007/978-3-030-85315-0_8
  13. [13]Pierre-Malo Deniélou, Nobuko Yoshida, Andi Bejleri, and Raymond Hu. 2012. Parameterised Multiparty Session Types. Log. Methods Comput. Sci. 8, 4 (2012). doi:10.2168/LMCS-8(4:6)2012DOI
  14. [15]Andrew K. Hirsch and Deepak Garg. 2022. Priouette: higher-order typed functional choreographies. Proc. ACM Program. Lang. 6, POPL (2022), 1–27. doi:10.1145/3498684DOI
  15. [16]Kohei Honda, Nobuko Yoshida, and Marco Carbone. 2008. Multiparty asynchronous session types. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7-12, 2008, George C. Necula and Philip Wadler (Eds.). ACM, 273–284. doi:10.1145/1328438.1328472DOI
  16. [17]Kohei Honda, Nobuko Yoshida, and Marco Carbone. 2016. Multiparty Asynchronous Session Types. J. ACM 63, 1 (2016), 91–9:67. doi:10.1145/2827695DOI
  17. [18]Lovro Lugović and Sung-Shik Jongmans. 2024. Klor: Choreographies in Clojure. https://github.com/lovrosdu/klor.
  18. [19]Yasuhiko Minamide, Greg Morrisett, and Robert Harper. 1996. Typed Closure Conversion. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, 271–283. doi:10.1145/237721.237791DOI
  19. [20]Fabrizio Montesi. 2013. Choreographic Programming. Ph.D. Thesis. IT University of Copenhagen. https://www.fabriziomontesi.com/files/choreographic-programming.pdf.
  20. [21]Fabrizio Montesi. 2023a. Errata for Introduction to Choreographies. https://www.fabriziomontesi.com/introduction-to-choreographies/#Errata Archived at https://web.archive.org/save/https://www.fabriziomontesi.com/introduction-to-choreographies/.
  21. [22]Fabrizio Montesi. 2023b. Introduction to Choreographies (1st ed.). Cambridge University Press, Cambridge.DOI
  22. [23]Kirstin Peters, Uwe Nestmann, and Ursula Goltz. 2013. On Distributability in Process Calculi. In Programming Languages and Systems - 22nd European Symposium on Programming, ESOP 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings (Lecture Notes in Computer Science, Vol. 7792), Matthias Felleisen and Philippa Gardner (Eds.). Springer, 310–329. doi:10.1007/978-3-642-37036-6_18DOI
  23. [24]Kirstin Peters and Nobuko Yoshida. 2024. Separation and Encodability in Mixed Choice Multiparty Session Types. In Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, July 8-11, 2024, Pawel Sobocinski, Ugo Dal Lago, and Javier Esparza (Eds.). ACM, 62:1–62:15. doi:10.1145/3661814.3662085DOI
  24. [25]Dan Plyukhin, Marco Peressotti, and Fabrizio Montesi. 2024. Ozone: Fully Out-of-Order Choreographies. In 38th European Conference on Object-Oriented Programming, ECOOP 2024, Vienna, Austria, September 16-20, 2024 (LIPIcs, Vol. 313), Jonathan Aldrich and Guido Salvaneschi (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 31:1–31:28. doi:10.4230/LIPIcs.ECOOP.2024.31
  25. [26]Johannes Åman Pohjola, Alejandro Gómez-Londoño, James Shaker, and Michael Norrish. 2022. Kalas: A Verified, End-To-End Compiler for a Choreographic Language. In 13th International Conference on Interactive Theorem Proving (ITP 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 237), June Andronick and Leonardo de Moura (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 27:1–27:18. doi:10.4230/LIPIcs.ITP.2022.27DOI
  26. [27]Xueying Qin, Marco Peressotti, and Fabrizio Montesi. 2026. Mech: Mechanised Choreographic Programming. CoRR abs/2607.15174 (2026). arXiv:2607.15174 doi:10.48550/ARXIV.2607.15174DOI
  27. [28]Ashley Samuelson, Andrew K. Hirsch, and Ethan Cecchetti. 2025. Choreographic Quick Changes: First-Class Location (Set) Polymorphism. Proc. ACM Program. Lang. 9, OOPSLA2 (2025), 1783–1808. doi:10.1145/3763114DOI
  28. [29]Alceste Scalas and Nobuko Yoshida. 2019. Les is more: multiparty session types revisited. Proc. ACM Program. Lang. 3, POPL (2019), 30:1–30:29. doi:10.1145/3290343DOI
  29. [30]Gan Shen, Kunisha W. and Kuper. 2023. HasChor: Functional Choreographic Programming for All (Functional Pearl). Proc. ACM Program. Lang. 7, ICFP (2023), 541–565. doi:10.1145/3607849DOI
  30. [31]The matlab Community. 2020. The Lean Mathematical Library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020). ACM, 367–381. doi:10.1145/3372885.3373824
  31. [32]Dawit Legesse Tirore, Jesper Bengtson, and Marco Carbone. 2025. Multiparty Asynchronous Session Types: A Mechanised Proof of Subject Reduction. In 39th European Conference on Object-Oriented Programming, ECOOP 2025, Bergen, Norway, June 30 - July 2, 2025 (LIPIcs, Vol. 333), Jonathan Aldrich and Alexandra Silva (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 31:1–31:30. doi:10.4230/LIPIcs.ECOOP.2025.31DOI
  32. [33]Rob J. van Glabbeek, Ursula Goltz, and Jens-Wolfhard Schicke. 2008. On Synchronous and Asynchronous Interaction in Distributed Systems. In Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings (Lecture Notes in Computer Science, Vol. 5162), Edward Ochmanski and Jerzy Tyszkiewicz (Eds.). Springer, 16–35. doi:10.1007/978-3-540-85238-4_2DOI

Paper details

vlnc:W_nrf6rrgk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Sol 6.1, Astra 6

View statement
Looking for related papers…
Contents