Mixed Choice in Asynchronous Multiparty Session Types Laura Bocchi, Raymond Hu, Adriana Laura Voinea, Simon Thompson Abstract . We present a multiparty session type (MST) framework with asynchronous mixed choice (MC). We propose a core construct for MC that allows transient inconsistencies in protocol state between distributed participants, but ensures all participants can always eventually reach a mutually consistent state. We prove the correctness of our system by establishing a progress property and an operational correspondence between global types and distributed local type projections. Based on our theory, we implement a practical toolchain for specifying and validating asynchronous MST protocols featuring MC, and programming compliant gen_statem processes in Erlang/OTP. We test our framework by using our toolchain to specify and reimplement part of the amqp_client of the RabbitMQ broker for Erlang. 1. Introduction Multiparty session types (MST) ( 30 ) is a typing discipline for concurrent processes that interact via message passing in communication sessions. The main idea is that an MST communication protocol can be statically checked for communication safety , i.e., freedom from fundamental errors such as reception errors (receiving unexpected messages), deadlocks (wait-for cycles) and orphan messages (messages that the receiver will never attempt to consume). MST is an active area of research due to its potential to offer programmatic techniques for safe specification and lightweight verification of communication protocols in concurrent and distributed systems. The key challenges being tackled include expressiveness of the types, tractability of the metatheory, and practicality of session-based programming and verification methods. These challenges are accentuated in the setting of distributed systems (DS) where communications are inherently asynchronous and failure is the norm. This paper tackles a crucial problem that concerns all of the above challenges: the notion of mixed choice in asynchronous MST. In classical MST ( 30 ; 4 ; 21 ) , the construct for choice in a protocol, called a directed choice , looks as follows. \mathtt{p}\mathbin{\rightarrowtriangle}\mathtt{q}:\{a_{i}.\mathtt{G}_{i}\}_{i\mathclose{\in}I} It specifies that a participant \mathtt{p} makes an internal choice to send one of the a_{i} messages to \mathtt{q} and continue in protocol G_{i} . Participant \mathtt{q} receives the a_{i} as an external choice and continues in G_{i} correspondingly. Some systems (e.g., ( 43 ; 44 ) ) support generalised choice constructs that allow the a_{i} to be sent to different \mathtt{q}_{i} . However, the key point remains that the choice is directed by \mathtt{p} . By contrast, this paper develops the following construct for mixed choice. \mathtt{q}\mathbin{\rightarrowtriangle}\mathtt{p}:a_{1}.\mathtt{G}_{1}\penalty\ \penalty\ \triangleright\penalty\ \penalty\ \mathtt{p}\mathbin{\rightarrowtriangle}\mathtt{q}:a_{2}.\mathtt{G}_{2} It specifies that \mathtt{p} and \mathtt{q} each independently face a choice between a mix of input and output actions: \mathtt{q} faces a mixed choice between sending a_{1} on the left and receiving a_{2} on the right, and vice versa for \mathtt{p} . In an asynchronous setting, this means that \mathtt{q} may opt to send a_{1} and continue in protocol G_{1} concurrently with \mathtt{p} opting to send a_{2} and continue in G_{2} . In this way, asynchronous mixed choices inherently describe a form of race condition, which classical MST intentionally prohibits outright because directed choice syntactically partitions all choices as input or output only. Yet such race conditions are useful and important in many real applications. Indeed, much recent research on improving the expressiveness and practicality of MST has touched on aspects of mixed choice, including work on exceptions ( 10 ; 57 ; 28 ) , interrupts ( 23 ; 18 ) , timing ( 38 ) and timeouts ( 49 ; 32 ) , failure handling ( 1 ; 3 ; 2 ; 8 ) , and fault-tolerance ( 58 ; 50 ) . These works (implicitly) involve patterns where a participant has the option on one hand to asynchronously output a message, while on the other hand it is simultaneously prepared for some input event, say, catching a concurrent channel exception, or receiving a criss-crossing interrupt or timeout message, or handling the failure of some other participant. The fundamental problem in reasoning about mixed choice in MST is that it allows participants to diverge in their local views of the protocol during execution. The insight of this paper is that communication safety can be achieved despite transient inconsistencies in distributed protocol state depending on how participants react to race-y messages and interact to resolve conflicts. Contributions and roadmap This paper presents the following contributions. • We introduce mMST , the first theory of global and local MST with an explicit construct for asynchronous mixed choice . To date, mixed choices in asynchronous sessions have only been partially expressed through specific-purpose constructs for exceptions, failure handling and so forth. By contrast, we present a general-purpose core theory of mixed choices that captures and unifies the fundamental essence of such ad hoc constructs. We propose an asymmetric design for mixed choice that statically ensures participants can eventually resolve the inherent race conditions through explicit interactions and agree on how the protocol should proceed. • We establish the correctness of mMST by proving a progress property for our mixed choice types, and an operational correspondence between global types and the corresponding system of local types. Together these guarantee that every non-terminated participant in an mMST protocol can always progress and that its behaviour is always protocol-compliant. Our results lay general foundations for a more flexible and practical concept of multiparty sessions that allows participants to deal with discrepancies in their distributed views of the protocol and safely converge on a consistent outcome. • We apply our theory by implementing a prototype toolchain for specifying and programming mMST-based protocols as gen_statem programs in Erlang/OTP. We test the expressiveness and practicality of mMST by using our toolchain to implement coordination protocols in the Erlang client of the RabbitMQ message broker, as well as a selection of examples from MST literature augmented with mixed choices. Section 2 gives a high-level overview of our mixed choice construct. Sections 3 and 4 present our theory and its formal properties. Section 5 describes our toolchain for Erlang, our RabbitMQ use case and other examples. Section 6 discusses related work, limitations and future work. Full details and proofs are available in the appendix. 2. Overview Our overall framework comprises two main stages. • Specification and static validation of a source mMST protocol based on our formal theory. • Implementation of each role in the asynchronous protocol in Erlang using correct-by-construction modules generated from the source protocol. The following two subsections illustrate the key concepts in each stage using a practical example. ⬇ 1 // Exception, Interrupt, etc. similar 2 global protocol Timeout ( 3 role A , role B , role C ) { 4 mixed { // "Left-hand" side (LHS) 5 a1 () from A to B ; 6 a2 () from A to C ; 7 a3 () from B to C ; 8 a4 () from B to A ; 9 a5 () from C to A ; 10 } or { // "Right-hand" side (RHS) 11 TOa () from B to A ; 12 TOc () from B to C ; 13 } } A B C 1,!a_{\mathtt{1}} 2,!a_{\mathtt{2}} 3,?a_{\mathtt{4}} 4,?a_{\mathtt{5}} 1,{}?a_{\mathtt{1}} 2,{}!a_{\mathtt{2}} 3,{}!a_{\mathtt{4}} 1,?a_{\mathtt{2}} 2,?a_{\mathtt{3}} 3,!a_{\mathtt{5}} \bullet a_{1} a_{2} a_{3} a_{4} a_{5} A B C 1,!a_{\mathtt{1}} 2,!a_{\mathtt{2}} 3,?^{*}\mathtt{TOa} 1,!^{*}\mathtt{TOa} 5,\mathsf{gc} 5,!\mathtt{TOc} 1,?^{*}\mathtt{TOc} 4,\mathsf{gc} a_{1} a_{2} \mathtt{TOa} \mathtt{TOc} Figure 1. A multiparty timeout pattern as a safe mMST protocol using asynchronous mixed choice. 2.1. Asymmetric Mixed Choice in Asynchronous MST Our toolchain takes mMST protocols written in our extension of the Scribble protocol language ( 60 ; 35 ) . Communications are asynchronous: interactions are non-blocking on the sender side, while the receiver side blocks until a message is available for reading. This means a sender moves ahead in the protocol immediately after dispatching a message without waiting for the message to be received. Messages are delivered in order of dispatch in each direction between each pair of roles; receivers read messages from the expected sender in a FIFO manner. This model reflects our target Erlang programs and wider domains such as TCP-based Internet applications and Web services. Figure 1 (left) illustrates a small protocol called Timeout involving three participants, whose behaviour is abstracted in MST as roles . The syntax of our mixed choice (MC) construct is: mixed { /* "Left-hand" side (LHS) */ } or { /* "Right-hand" side (RHS) */ } The protocol features an MC between role A on the LHS and B on the RHS. It expresses a typical timeout pattern where A has the option to send message a1 to B (and proceed asynchronously) on the LHS, but it must also be prepared to handle the potentially concurrent timeout message TOa from B on the RHS. Conversely, B has the option to wait for the a1 message on the LHS, or give up waiting and asynchronously send TOa on the RHS. Depending on how A and B proceed, role C must be prepared to handle one or both of the a2 from A and the TOc from B . We summarise the key concepts in the design of our MC and how we ensure MST safety. • Our MC is an asymmetric construct. In each MC, we designate the sender on the RHS as a special role that we refer to as the observer of the MC. The LHS can be considered a default or speculative branch, which can be asynchronously superceded by the RHS on the instigation of the observer. • We identify a notion of commitment of roles to an MC branch (LHS or RHS). Commitment means that the inherent race condition of an MC has been resolved from the perspective of that role and it knows the protocol will henceforth proceed only in that branch. An MC starts with no roles committed to either branch. Regardless of (speculative) interactions between other roles in the LHS, the first action by the observer in an MC (input on the LHS or output on the RHS) commits the observer to that branch. Any subsequent action by another role \mathtt{r} , where the action causally depends on the observer, commits \mathtt{r} to the same branch. • Protocol validation due to our formal theory ensures that however a protocol (speculatively) proceeds, all eventual commitments are monotonic and always consistent with the observer. To illustrate, Figure 1 (right) depicts two possible executions of the protocol. For now, the reader can focus on the arrows and the blue labels; the grey annotations will be explained in Sec. 2.2 . • The upper chart is a run where observer B opts to receive a1 and follow A on the LHS, i.e., it does not raise the timeout. While A and C may proceed asynchronously on the LHS, the observer B is the first role to commit when it consumes the a1 . In turn C commits to the LHS when it consumes the a3 from B , and A commits when it consumes the a4 . Although the a5 can arrive on the LHS at A before the a4 , A must consume the a4 (and commit to the LHS) first following the protocol. • The lower chart is a run where observer B opts to overrule A and raise the timeout by sending TOa , which commits B to the RHS. Although A and C may be concurrently engaged in interactions on the LHS, role A eventually receives the TOa , causing it to switch from the LHS and commit to the RHS. Similarly, C switches and commits to the RHS when it receives the TOc . Stale message purging. The latter of the above cases demonstrates that supporting mixed choices safely in asynchronous MST requires one further key concept. Due to asynchrony, actions performed by one role may concurrently render other messages that are buffered or being sent obsolete. For instance, in the lower chart, the a1 message ‘criss-crosses’ with TOa and arrives at B after B has already committed to the RHS. From B ’s perspective, sending the TOa renders the (already in-transit) a1 obsolete; in such cases, we refer to messages like a1 as stale messages. Similarly, the receipt of TOc by C renders the a2 stale. Our theory formalises a runtime mechanism that allows stale messages to be automatically purged transparently to the user program; e.g., in the case mentioned above, the runtime at B (resp. at C ) will transparently purge the a1 that arrives after sending TOa (resp. the a2 after receiving TOc ). Crucially, stale message purging can be safely performed by the local runtime of each distributed participant using only knowledge available to that participant. The notion of stale messages and purging never arises in classical MST. Our transparent purging mechanism could be considered a message passing analogy to garbage collection of stale objects in programming languages with automated memory management (such as Erlang). MC protocol validation. For reference, the Timeout protocol written in our formal notation for global types ( Section 3 ) is as follows. The \triangleright separates the LHS and RHS of the MC. The additional blue colouring indicates the points at which the roles become committed. \mathtt{A}\mathbin{\rightarrowtriangle}\mathtt{B}:a_{1}\,.\,\mathtt{A}\mathbin{\rightarrowtriangle}\mathtt{C}:a_{2}\,.\,\mathtt{\color[rgb]{0,0,1}B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}C}:a_{3}\,.\,\mathtt{B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}A}:a_{4}\,.\,\mathtt{C}\mathbin{\rightarrowtriangle}\mathtt{A}:a_{5}\,.\,\mathtt{end}\;\;\triangleright\;\;\mathtt{\color[rgb]{0,0,1}B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}A}:\mathtt{TOa}\,.\,\mathtt{B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}C}:\mathtt{TOc}\,.\,\mathtt{end} ✓ Our static protocol validation ensures that role commitments are always consistent with the observer and that role termination is safe (as illustrated in the earlier example runs). By contrast, the below (renaming TOc ) is rejected because commitment is ambiguous for C . \mathtt{A}\mathbin{\rightarrowtriangle}\mathtt{B}:a_{1}\,.\,\mathtt{A}\mathbin{\rightarrowtriangle}\mathtt{C}:a_{2}\,.\,\mathtt{\color[rgb]{0,0,1}B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}C}:{\color[rgb]{1,0,0}a_{3}}\,.\,\mathtt{B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}A}:a_{4}\,.\,\mathtt{C}\mathbin{\rightarrowtriangle}\mathtt{A}:a_{5}\,.\,\mathtt{end}\;\;\triangleright\;\;\mathtt{\color[rgb]{0,0,1}B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}A}:\mathtt{TOa}\,.\,\mathtt{B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}C}:{\color[rgb]{1,0,0}a_{3}}\,.\,\mathtt{end} ✗ The below (dropping the a_{3} ) is also rejected because C reaches end without committing on the LHS. \mathtt{A}\mathbin{\rightarrowtriangle}\mathtt{B}:a_{1}\,.\,\mathtt{A}\mathbin{\rightarrowtriangle}\mathtt{C}:a_{2}\,.\,\mathtt{\color[rgb]{0,0,1}B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}A}:a_{4}\,.\,\mathtt{C}\mathbin{\rightarrowtriangle}\mathtt{A}:a_{5}\,.\,{\mathtt{end}}\;\;\triangleright\;\;\mathtt{\color[rgb]{0,0,1}B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}A}:\mathtt{TOa}\,.\,\mathtt{B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}C}:\mathtt{TOc}\,.\,\mathtt{end} ✗ However, the below (dropping the a_{4} ) is accepted; A can safely commit on the LHS because it has a transitive causal dependency with observer B via C . \mathtt{A}\mathbin{\rightarrowtriangle}\mathtt{B}:a_{1}\,.\,\mathtt{A}\mathbin{\rightarrowtriangle}\mathtt{C}:a_{2}\,.\,\mathtt{\color[rgb]{0,0,1}B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}C}:a_{3}\,.\,\mathtt{C}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}A}:a_{5}\,.\,\mathtt{end}\;\;\triangleright\;\;\mathtt{\color[rgb]{0,0,1}B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}A}:\mathtt{TOa}\,.\,\mathtt{B}\mathbin{\rightarrowtriangle}\mathtt{\color[rgb]{0,0,1}C}:\mathtt{TOc}\,.\,\mathtt{end} ✓ Altogether, the design of our asynchronous MC, the concepts of observer and commitment and the protocol validation guarantee that every role that has not safely terminated will continue progressing through the protocol as expected. As an advance pointer, the main conditions checked by the protocol validation (which we refer to as awareness ) and the progress property for global types are formally defined and established in Section 3.3 . On the expressiveness of mMST, consider again the criss-crossing pattern between A and B in the lower chart of Figure 1 (right). By contrast, the conservative syntactic structure of classical MST ( 22 ; 31 ) implicitly precludes all such patterns where asynchronous messages criss-cross between a pair of roles in opposing directions. The complications introduced by these patterns – such as the inherent race conditions, stale messages, and the mechanisms required to resolve these – are why reasoning about safety of mixed choices in asynchronous MST (and DS in general!) is a difficult challenge, and has remained an open problem for MST. We have used the small Timeout example to introduce our MC and the key concepts. Nevertheless, it demonstrates how mMST supports the fundamental communication pattern underlying various important DS constructs, including exceptions, interrupts and failure handling, as found in many real-world applications. Our MC provides a core building block for expressing these constructs in MST. Sections 3 and 5.2 include and summarise a range of further such examples that involve combining MC with the standard directed choice of MST, recursion and nested MCs. 2.2. Mixed Choice MST protocols in Erlang Erlang is a concurrent, dynamically typed functional programming language designed for implementing applications out of message passing processes. It is used in major applications and platforms such as WhatsApp and RabbitMQ. Its emphasis on building fault-tolerant distributed systems makes it a good target for applying and testing mMST. Erlang/OTP has built-in support for a set of core design patterns, known as behaviours , for implementing processes. In this paper, we target the gen_statem behaviour that provides a generic framework for implementing state machines. A process is formed by combining the provided generic state machine behaviour module with a user-written module of callback functions for handling events and state transitions according to the required application-specific logic. Based on our theory, we have implemented a toolchain for specifying and implementing mMST protocols as gen_statem processes. Our toolchain involves these steps. • The user writes the source global protocol (e.g., Timeout in Figure 1 ) using our mMST extension of Scribble and uses the tool to validate it based on our formal conditions. • The tool internally projects valid global protocols to a local protocol for each role. The tool represents a local protocol as an Event-Driven Finite State Machine (EFSM) that matches the programming abstractions of gen_statem (see below). • From each EFSM, the tool generates (i) a correct-by-construction protocol- and role-specific gen_statem behaviour module, and (ii) a corresponding template callback module for the programmer to use and adapt as required to complete the process definition. Global-to-local projection A local protocol is the view of the protocol from a specific role. Projecting a global protocol to a set of local protocols, one for each role, yields a distributed model. In our formal notation, the projected local types for Timeout are: \begin{array}[]{lllll}\mathtt{Timeout}\upharpoonright\mathtt{A}=&\mathtt{B}\oplus a_{1}\,.\,\mathtt{C}\oplus a_{2}\,.\,\phantom{\mathtt{B}\,\&\,a_{3}\,.\,}\mathtt{B}\,\&\,a_{4}\,.\,\mathtt{C}\,\&\,a_{5}\,.\,\mathtt{end}&\triangleright&\mathtt{B}\,\&\,\mathtt{TOa}\,.\,\phantom{\mathtt{B}\oplus\mathtt{TOc}\,.\,}\mathtt{end}\\ \mathtt{Timeout}\upharpoonright\mathtt{B}=&\mathtt{A}\,\&\,a_{1}\,.\,\phantom{\mathtt{A}\,\&\,a_{2}\,.\,}\mathtt{C}\oplus a_{3}\,.\,\mathtt{A}\oplus a_{4}\,.\,\phantom{\mathtt{C}\,\&\,a_{5}\,.\,}\mathtt{end}&\triangleright&\mathtt{A}\oplus\mathtt{TOa}\,.\,\mathtt{C}\oplus\mathtt{TOc}\,.\,\mathtt{end}\\ \mathtt{Timeout}\upharpoonright\mathtt{C}=&\phantom{\mathtt{A}\,\&\,a_{1}\,.\,}\mathtt{A}\,\&\,a_{2}\,.\,\mathtt{B}\,\&\,a_{3}\,.\,\phantom{\mathtt{B}\,\&\,a_{4}\,.\,}\mathtt{A}\oplus\,a_{5}\,.\,\mathtt{end}&\triangleright&\phantom{\mathtt{B}\oplus\mathtt{TOa}\,.\,}\mathtt{B}\,\&\,\mathtt{TOc}\,.\,\mathtt{end}\\ \end{array} The \triangleright separates the LHS and RHS of the projected mixed choices. The \oplus denotes an output-only choice (internal select), and \& denotes the dual input-only choice (external branch); in this simple example, the input/output-only choices are all unary. Section 4.3 proves that the behaviour of a projected local system corresponds to that of the global protocol. Projection thus entails that a protocol is realisable as a distributed system. EFSM representation The core abstraction of gen_statem is an Event-Driven Finite State Machine (EFSM). Transitions are described by 1 1 1 https://www.erlang.org/doc/system/statem.html State (S) \times Event (E) \rightarrow Action (A) \times State (S’) which can be read: if the current state is S and event E occurs, then perform action A and transition to successor state S’ – i.e., the transition is triggered by E and A is a consequent effect. Events may have external sources, such as the arrival of a message ( ? ), or internal ( \tau ), such as a local computation. Actions include sending ( ! ) messages and the empty action ( \epsilon ). In our mMST setting, a transition can also have the effect of switching from the LHS of an MC to commit to the RHS. 1 A 2 3 4 5 \tau/\mathtt{B}!a_{\mathtt{1}} \tau/\mathtt{C}!a_{\mathtt{2}} \mathtt{B}?a_{\mathtt{4}} \mathtt{C}?a_{\mathtt{5}} \mathtt{B?^{*}TOa} \mathtt{B?^{*}TOa} \mathtt{B?^{*}TOa} 1 B 2 3 4 \mathtt{A?}a_{\mathtt{1}} \tau/\mathtt{C!}a_{\mathtt{3}} \tau/\mathtt{A!}a_{\mathtt{4}} 5 \mathtt{A?}a_{\mathtt{1}}/\mathtt{A!^{*}TOa} \mathtt{\tau/A!^{*}TOa} \tau/\mathtt{C!TOc} 1 C 2 3 4 \mathtt{B?}a_{\mathtt{2}} \mathtt{A?}a_{\mathtt{3}} \tau/\mathtt{A!}a_{\mathtt{5}} \mathtt{B?^{*}TOc} \mathtt{B?^{*}TOc} 4 Transition labels: Event ‘/’ Action Event: ‘ \tau ’ internal ‘ ? ’ external msg. arrival Action: ‘ ! ’ send \;|\; ‘ \epsilon ’ empty ? -only labels are short for ? / \epsilon ∗ means switch to RHS of MC Figure 2. Local mMST protocols for each role of Timeout as EFSMs in Erlang gen_statem . Figure 2 depicts the EFSM generated by our tool for each role of Timeout . The notation e/\alpha on the transitions means event e triggers the transition and action \alpha is performed; an e on its own is shorthand for e/\epsilon . For example, the \tau/\mathtt{B}!a_{\mathtt{1}} from state 1 of \mathtt{A} means that \mathtt{A} can internally decide to send a_{\mathtt{1}} to \mathtt{B} (and transition to 2 ). In \mathtt{B} , the two transitions from state 1 with event \mathtt{A}?a_{\mathtt{1}} mean that if message a_{\mathtt{1}} arrives as an external event, \mathtt{B} can either do \mathtt{A}!^{*}\mathtt{TOa} and transition to 4 , or transition to 2 (with the empty action). Note, the ∗ annotation (as also occurs in the text below) indicates the transitions that switch from the LHS to the RHS of the MC. Classical MST permits only three kinds of local states: input-only (branch), output-only (select), and terminal; e.g., state 4 in \mathtt{A} is a branch, and 3 in \mathtt{C} is a select (again, both unary in this simple example). By contrast, the more expressive local behaviours enabled by our asynchronous MC can also be seen in the above EFSMs. As mentioned, observer B faces an internal MC in state 1 indicated by the mix of \tau/!^{*} and ?/\epsilon transitions induced by its RHS and LHS, respectively, yielding the timeout behaviour described at the start of Section 2.1 . On the other hand, A faces an external MC in state 1 as indicated by its mix of ?^{*}/\epsilon and \tau/! transitions: A can either (wait to) receive the TOa (and switch to the RHS), or internally decide (by some internal event \tau ) to send a_{\mathtt{1}} and proceed to 2 . Our formal semantics allows both options, but an implementation may (e.g.) give priority to the former case if \mathtt{TOa} has already arrived. Note how A is forced to eventually commit to either the LHS or RHS (in accordance with B ) by state 3 at the latest by receiving a_{\mathtt{4}} or \mathtt{TOa} . We give a couple of further comments on the richer behaviours expressed by our MC. First, note that external MCs may take various forms: e.g., both states 1 in A and 1 in C are external MCs featuring ?^{*} , but the former is mixed with a \tau whereas the latter is mixed with an ? -event. Second, note that the top-level roles of the MC are A and B , but their localised (projected) behaviours in the MC are not direct duals; e.g., state 3 in A is an external MC between a_{4} and \mathtt{TOa} that has no direct counterpart in B (i.e., there is no internal MC featuring a_{4} in B ). Additionally, ?^{*}\mathtt{TOa} events are spread over states 1 , 2 and 3 in A ; whereas in B , the !^{*}\mathtt{TOa} occurs only in 1 , although in two different transitions since B can choose to raise the timeout either before ( \tau ) or after ( ? ) the a_{\mathtt{1}} has arrived. These behaviours are considerably more exotic than those supported in classical MST and speak to the challenge of reasoning about asynchronous MC theoretically and practically. Programming mMST-based processes in Erlang. Our toolchain uses the EFSMs to generate two Erlang modules per role for the programmer(s) to work with. The role module (RM) provides a customised gen_statem behaviour that is specialised to the source protocol and role. The programmer can consider it as part of the runtime and does not need to use it directly. The other, called the callback module (CM), is a template module of callback functions that the RM delegates to for handling event occurrences and performing state transition actions. The CM is generated with minimal placeholder code that the programmer can modify and extend with the required application-specific logic. The RM and CM together form a protocol- and role-specific mMST process. A set of processes comprising one for each role forms a complete application. ⬇ 1 % Extract from role A 2 s1 ( internal , a1 , Data ) -> 3 gen_a : send_s1_a1 ( BPid , Data ), { next_state , s2 , 4 Data , [{ next_event , internal , a2 }]}; 5 s1 ( cast , { BPid , ’TOa’ }, Data ) -> { stop , normal , Data }. 6 7 s2 ( internal , a2 , Data ) -> 8 gen_a : send_s2_a2 ( CPid , Data ), { next_state , s3 , Data }; 9 s2 ( cast , { BPid , ’TOa’ }, Data ) -> { stop , normal , Data }. 10 11 s3 ( cast , { BPid , a4 }, Data ) -> { next_state , s4 , Data }; 12 s3 ( cast , { BPid , ’TOa’ }, Data ) -> { stop , normal , Data }. 13 14 s4 ( cast , { CPid , a5 }, Data ) -> { stop , normal , Data }. 15 16 17 % Extract from role B 18 s1 ( internal , ’TOa’ , Data ) -> 19 case make_choice_TOa ( Data ) of 20 1 -> { keep_state , Data }; 21 2 -> gen_b : send_s1_TOa ( APid , Data ), { next_state , s3 , 22 Data , [{ next_event , internal , ’TOc’ }]} 23 end ; % Continued on the right ⬇ 24 % Continued from the left 25 s1 ( cast ,{ APid , a1 }, Data ) -> 26 case make_choice_a1 ( Data ) of 27 1 -> { next_state , s2 , Data , 28 [{ next_event , internal , a3 }]}; 29 2 -> gen_b : send_s1_TOa ( APid , Data ), 30 { next_state , s5 , Data , 31 [{ next_event , internal , ’TOc’ }]} 32 end . 33 34 s5 ( internal , ’TOc’ , Data ) -> 35 gen_b : send_s5_TOc ( CPid , Data ), 36 { stop , normal , Data }. 37 38 s2 ( internal , a3 , Data ) -> 39 gen_b : send_s2_a3 ( CPid , Data ), { next_state , s3 , 40 Data , [{ next_event , internal , a4 }]}. 41 42 s3 ( internal , a4 , Data ) -> 43 gen_b : send_s3_a4 ( APid , Data ), 44 { stop , normal , Data }. 45 46 Figure 3. Extracts from the user-facing callback modules generated for A and B in the Timeout protocol. Figure 3 shows code from the CMs as generated for roles A and B . As per their respective EFSMs ( Figure 2 ), they feature callback state functions (e.g., s1 , s2 , etc.) for handling state transitions according to event occurrences. The callbacks are fired (from the RM) based on the current state and by pattern matching against the event, which may come from an internal (locally triggered transitions, such as timeout decisions) or external (incoming messages) source. For instance, in A , state function s1 represents an external MC corresponding to state 1 (for A in Figure 2 ): A may either send a1 to B (the internal clause), or receive ‘TOa’ from B (the cast clause), corresponding to the \mathtt{\tau/B!a_{1}} and \mathtt{B?^{*}TOa} transitions, respectively. In B , the function s1 represents an internal MC. In the first clause ( internal ), B handles the internal event from the generated template function make_choice_TOa by which it decides whether to remain in the current state ( keep_state ) and wait to receive a1 , or transition to s2 by sending ‘TOa’ to A (cf. \mathtt{\tau/A!^{*}To} ). Generally, the programmer will modify/replace such template decision functions according to the required application logic. In the second clause ( cast ), B receives the message a1 from A , and based on template function make_choice_a1(Data) , either transitions (cf. \mathtt{A}?a_{\mathtt{1}}\mathtt{/A!^{*}TOa} ) to s3 and schedules an internal event a2 , or sends ‘TOa’ to A and transitions (cf. \mathtt{A}?a_{\mathtt{1}} ) to s2 . Section 5 demonstrates the internals of the RM that fires the callbacks in the above CM. In short, our tool generates the RM by instantiating the default gen_statem behaviour with the required EFSM structure (states, events, actions, and transitions); this is correct-by-construction and the programmer should not modify the RM. Following our formal semantics, the RM is also generated to encapsulate the (again, correct-by-construction) runtime mechanisms for handling MC commitment, LHS-to-RHS switching, and stale message purging specifically for the source protocol and role. The programmer can assume these mechanisms are provided and correct when working on the CM. Recall the example executions in Figure 1 (right). The grey annotations denote the current state and relevant event/action at each role according to their EFSMs in Figure 2 ; e.g., 1,!a_{\mathtt{1}} means in state 1 , send message a_{\mathtt{1}} . Stale message purging, denoted by \mathsf{gc} in Figure 1 , is handled internally by the RM; we exclude purge actions from our depictions of EFSMs as they are transparent to the programmer. User processes do not consume stale messages, so they must be purged from the input buffer to prevent interference with future receives (given the FIFO nature of inputs). 2.3. Properties of mMST We end this overview by summarising the properties of our framework with advance pointers (a roadmap) to the relevant parts of our formal theory. Section 3 formalises the syntax and metatheoretical LTS semantics of our global types with mixed choice and the notion of committing messages in MCs. It defines the conditions checked by protocol validation on protocol structure ( well-formedness of committing messages, balance of roles across choice branches) and on inter-role dependencies in MCs ( awareness ). Section 3.3 proves that valid protocols enjoy a per-role progress property and that their roles are always consistent in their commitments ( coherence ). Section 4 formalises the syntax and LTS semantics of distributed local types and asynchronous message queues, the projection from global to local types, and the runtime mechanism for stale message purging . Section 4.3 proves an operational correspondence in both directions between valid projectable global types and local systems that preserves projection . The operational correspondence (i.e., preservation of projection) and progress properties together safely entail that local roles never get stuck in a deadlock nor (noting the FIFO nature of communications in the local type LTS) due to receiving an unexpected message. Section 4.4 further proves orphan message freedom. As discussed, our practical toolchain is implemented to perform protocol validation (conservatively, see Section 5.1 ) and projection following our formal theory. It is implemented to perform a correct-by-construction translation from local projections to EFSMs and generation of gen_statem modules to transfer the above correctness properties to Erlang processes. The usage contract is that the programmer should not modify the generated RM and must use the CM according to the generated structures. The RM is generated with some internal runtime checks against the programmer supplying an invalid CM. 3. Global Types The syntax of global types \mathtt{G} is defined by the grammar below: \begin{array}[]{lll}\mathtt{G}&::=&\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S}\mid\mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ { { \lxSVG@setdash{0.0pt}\lx@inpgf@ignorespaces\lxSVG@miterjoin\lx@inpgf@ignorespaces{} {} {} {} \lxSVG@fillstroke}} }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\,{\color[rgb]{0,0,1}S}\mid\mu\mathtt{t}.\mathtt{G}\mid\mathtt{t}\mid\mathtt{end}\mid\mathtt{q}\rightarrowtriangle\mathtt{p}:{\color[rgb]{0,0,1}S_{1}}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S_{2}}\mid\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2}\\ {\color[rgb]{0,0,1}S}&::=&\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\end{array} The first five terms are standard ( 27 ) . We recall that \mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S} is an interaction where \mathtt{p} is the sender and \mathtt{q} is the receiver. Term {\color[rgb]{0,0,1}S} specifies a set of choices: \mathtt{p} can send \mathtt{q} one of the labels a_{i} (for i\in I ) and the protocol continues as \mathtt{G}_{i} . The message in-transit type \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\,{\color[rgb]{0,0,1}S} stands for a state where \mathtt{p} has sent label a_{k} but \mathtt{q} has not yet received it (asynchronous communication). Term \mu\mathtt{t}.\mathtt{G} is a recursive definition 2 2 2 We adopt iso-recursive types for a lower level view of nested MC instantiation and straightforward implementation. and \mathtt{t} a recursive variable. The last two terms are new and model mixed choices (MC). The term \mathtt{q}\rightarrowtriangle\mathtt{p}:{\color[rgb]{0,0,1}S_{1}}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S_{2}} is an MC definition : we call \mathtt{q}\rightarrowtriangle\mathtt{p}:{\color[rgb]{0,0,1}S_{1}} the left-hand side block (LHS) of the MC and \mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S_{2}} the right-hand side block (RHS). Role \mathtt{p} is set to receive a message from \mathtt{q} in the LHS, but may decide to execute the RHS by sending a message to \mathtt{q} instead. We say that \mathtt{p} is the observer of the MC. We annotate MC definitions with a unique name c , which we may omit when it is not important. The term \mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2} is an active MC . To ensure that roles eventually agree on which block (LHS or RHS) to execute, we use a notion of commitment . Some actions are designated as committing (defined in Section 3.1 ). When a role executes a committing action within a block, it commits to that block, meaning that it can no longer perform any action (send or receive) in the other block. The semantics of global types use sets \mathcal{L} to keep track of the roles that are committed to the LHS, and \mathcal{R} to keep track those committed to the RHS. For convenience we may use the notation \mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c:\mathtt{p}}\mkern 1.0mu}\mathtt{G}_{2} and \mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c:\mathtt{p}}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2} assuming that \mathtt{G}_{1} and \mathtt{G}_{2} are of the form given by the grammar and that \mathtt{p} is the observer. For readability, we omit annotations c , \mathcal{L} or \mathcal{R} when not needed. A global type is initial if it has no messages in transit and no active MC. The set of roles of \mathtt{G} , denoted \mathtt{R}(\mathtt{G}) , is defined as usual except for the two new cases for MC: \mathtt{R}(\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathtt{G}_{2})=\mathtt{R}(\mathtt{G}_{1})\penalty\ \cup\penalty\ \mathtt{R}(\mathtt{G}_{2})\qquad\mathtt{R}(\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2})=\mathtt{R}(\mathtt{G}_{1})\setminus\mathcal{R}\penalty\ \cup\penalty\ \mathtt{R}(\mathtt{G}_{2})\setminus\mathcal{L} The roles of a MC definition are the roles in either of its sides. The case of active MC excludes the roles that have committed to the opposite side. This will be critical when defining progress, to characterise the roles that should continue on each side. We define a context environment \mathbf{C} : \mathbf{C}::=[\,\_\,]\mid\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S}\cup\{a.\mathbf{C}\}\mid\mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\,{\color[rgb]{0,0,1}S}\cup\{a_{k}.\mathbf{C}\}\mid\mathbf{C}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{G}\mid\mathtt{G}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathbf{C}\mid\mathbf{C}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathtt{G}\mid\mathtt{G}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathbf{C}\mid\mu\mathtt{t}.\mathbf{C} We say that \mathtt{G}^{\prime} is a subterm of \mathtt{G} (or is in \mathtt{G} ) if there exists \mathbf{C} such that \mathtt{G}=\mathbf{C}[\mathtt{G}^{\prime}] . We say that two subterms of \mathtt{G}_{1} and \mathtt{G}_{2} of \mathtt{G} are distinguished if \mathtt{G}=\mathbf{C}_{1}[\mathtt{G}_{1}]=\mathbf{C}_{2}[\mathtt{G}_{2}] implies \mathbf{C}_{1}\neq\mathbf{C}_{2} . We say that \mathtt{G} has an active MC \mathtt{G}_{1}\blacktriangleright\mathtt{G}_{2} if \mathtt{G}_{1}\blacktriangleright\mathtt{G}_{2} is a subterm of \mathtt{G} . Similarly for MC definitions. 3.1. Committing Set and Well-Formedness In this section we formally introduce the notion of commitment, by defining the committing set of a MC named c , that is the set of actions by which some role commits to either the LHS or to the RHS of c . The committing set is defined on initial global types. Intuitively, the committing actions of a MC are: (1) on the LHS, the first receive action by the observer, and all receive actions of a message from a committed sender, (2) on the RHS, all the first actions of a role on that side. For simplicity, we identify committing actions (e.g., \mathtt{p}\mathtt{q}?a ) using only their labels (e.g., a ). The committing set is therefore, a set of communication labels. In the following we denote with \mathtt{U}(\mathtt{G}) the standard unfold-all-once operation that unfolds once all recursive types in \mathtt{G} . We say that \mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{G}_{2} is the outermost occurrence of c in \mathtt{U}(G) if it is not a subterm of other MC definitions c in \mathtt{U}(G) . Given a global type \mathtt{q}\rightarrowtriangle\mathtt{p}:{\color[rgb]{0,0,1}S} with {\color[rgb]{0,0,1}S}=\{a_{i}.\mathtt{G}_{i}\}_{i\in I} , we use the notation \mathtt{labels}({\color[rgb]{0,0,1}S})=\{a_{i}\}_{i\in I} and \mathtt{types}({\color[rgb]{0,0,1}S})=\{\mathtt{G}_{i}\}_{i\in I} . Definition 3.1 (Committing set). Let \mathtt{G} be an initial global type. Let c be an MC definition in \mathtt{G} , and {\mathtt{q}\rightarrowtriangle\mathtt{p}:\,{\color[rgb]{0,0,1}S_{1}}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\,\mathtt{p}\rightarrowtriangle\mathtt{q}:\,{\color[rgb]{0,0,1}S_{2}}} be the outermost occurrence of c in \mathtt{U}(\mathtt{G}) . The committing set of c in \mathtt{G} , denoted \Downarrow^{c}\hskip-2.84526pt(\mathtt{G}) , is defined as follows: \begin{array}[]{l}\Downarrow^{c}\hskip-2.84526pt(\mathtt{G})\penalty\ \coloneq\penalty\ \mathtt{labels}({\color[rgb]{0,0,1}S_{1}}\,\cup\,{\color[rgb]{0,0,1}S_{2}})\penalty\ \penalty\ \cup\penalty\ \penalty\ \bigcup_{G\in\mathtt{types}({\color[rgb]{0,0,1}S_{1}})}\Downarrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}\{\mathtt{p}\}})\penalty\ \penalty\ \cup\penalty\ \penalty\ \bigcup_{G\in\mathtt{types}({\color[rgb]{0,0,1}S_{2}})}\Downarrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}\{\mathtt{p},\mathtt{q}\}})\end{array} where \Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C}) is an auxiliary function parameterized by the set C of committed roles, used to track dependency with other committing actions. In brief, the case for interactions is: \Downarrow^{c}\hskip-2.84526pt(\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S},{\color[rgb]{0.5,0.5,0.5}C})=\begin{cases}\mathtt{labels}({\color[rgb]{0,0,1}S})\penalty\ \cup\bigcup_{\mathtt{G}\in\mathtt{types}({\color[rgb]{0,0,1}S})}\Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C\cup\{\mathtt{q}\}})&(\mathtt{p}\in C\penalty\ \land\penalty\ \mathtt{q}\not\in C)\\ \bigcup_{\mathtt{G}\in\mathtt{types}({\color[rgb]{0,0,1}S})}\Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})&\text{otherwise}\end{cases} The case \Downarrow^{c}\hskip-2.84526pt(\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c^{\prime}}\mkern 1.0mu}\mathtt{G}_{2},{\color[rgb]{0.5,0.5,0.5}C}) returns \Downarrow^{c}\hskip-2.84526pt(\mathtt{G}_{1},{\color[rgb]{0.5,0.5,0.5}C})\penalty\ \cup\Downarrow^{c}\hskip-2.84526pt(\mathtt{G}_{2},{\color[rgb]{0.5,0.5,0.5}C}) if c^{\prime}\neq c , and the empty set otherwise. Finally, \Downarrow^{c}\hskip-2.84526pt(\mu\mathtt{t}.\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})\mathop{=}\Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C}) and \Downarrow^{c}\hskip-2.84526pt(\mathtt{t},{\color[rgb]{0.5,0.5,0.5}C})\mathop{=}\Downarrow^{c}\hskip-2.84526pt(\mathtt{end},{\color[rgb]{0.5,0.5,0.5}C})\mathop{=}\emptyset . Intuitively, \Downarrow^{c}\hskip-2.84526pt(\mathtt{G}) identifies the labels of {\color[rgb]{0,0,1}S_{1}}\cup{\color[rgb]{0,0,1}S_{2}} as the set of initial committing labels in c : the labels in {\color[rgb]{0,0,1}S_{1}} are committing for \mathtt{p} and labels in {\color[rgb]{0,0,1}S_{2}} are committing for both \mathtt{q} and \mathtt{p} . To these labels, we add those that depend on actions by \mathtt{p} on the RHS of c and \{\mathtt{p},\mathtt{q}\} on the LHS, by using the auxiliary function. The function \Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C}) traverses the syntactic structure of \mathtt{G} until it reaches \mathtt{t} , \mathtt{end} , or a nested occurrence of the same c (introduced by unfolding). In case \Downarrow^{c}\hskip-2.84526pt(\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S},{\color[rgb]{0.5,0.5,0.5}C}) all labels that are sent from a committed role \mathtt{p}\in C to a non-committed role \mathtt{q}\not\in C are regarded as committing. Unfolding \mathtt{U}(\mathtt{G}) is used to account for committing labels that are captured into a MC block only after recursive unfolding, as we illustrate in Example 3.2 . Example 3.2 (Label capture). Consider the recursive type \mathtt{G}_{c}=\mu\mathtt{t}.\,\mathtt{p}\rightarrowtriangle\mathtt{r}:{\color[rgb]{1,0,1}a}.(\mathtt{q}\rightarrowtriangle\mathtt{p}:b.\,\mathtt{t}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathtt{G}_{2}) where label a\mathop{\not\in}\mathtt{G}_{2} and hence does not appear directly in the MC. If we apply the auxiliary function in Definition 3.1 to \mathtt{G}_{c} itself (rather than its unfolding \mathtt{U}(\mathtt{G}_{c}) ) then a would not be included in the committing set of \mathtt{G}_{c} . However, after some steps that involve recursive unfolding, shown in ( 1 ), an occurrence of a is introduced on the LHS of the outer MC. This second occurrence of a is committing (it makes \mathtt{r} commit to the LHS of the outer MC). By using unfolding, Definition 3.1 correctly identifies a as committing. (1) \mathtt{G}_{c}\penalty\ \penalty\ \penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{}\hskip-3.44444pt^{*}}\penalty\ \penalty\ \penalty\ \penalty\ \mathtt{p}\rightarrowtriangle\mathtt{r}:{\color[rgb]{1,0,1}a}.(\mathtt{q}\rightarrowtriangle\mathtt{p}:b.{\color[rgb]{0,0,1}(\mu\mathtt{t}.\,\mathtt{p}\rightarrowtriangle\mathtt{r}:{\color[rgb]{1,0,1}a}.(\mathtt{q}\rightarrowtriangle\mathtt{p}:b.\,\mathtt{t}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathtt{G}_{2}))}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{G}_{2}) Well-formedness Global types where a label occurs multiple times, and where some occurrences are committing and some others are not, are problematic. A simple example is ( 2 ), where b appears twice, and is non-committing on the LHS of c while it is committing on the RHS. (2) \mathtt{G}_{\textrm{✗}}=\mathtt{q}\rightarrowtriangle\mathtt{p}:a.\,\mathtt{q}\rightarrowtriangle\mathtt{r}:{\color[rgb]{1,0,1}b}.\,\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:c.\,\mathtt{q}\rightarrowtriangle\mathtt{r}:{\color[rgb]{1,0,1}b}.\,\mathtt{G}_{2} It is critical that we avoid ambiguities such as those in ( 2 ), as they may lead to incorrect semantics for mixed choices. To address this, we introduce a well-formedness condition on initial global types, requiring that all occurrences of a label are exclusively either committing or non-committing. Well-formedness relies on the notion of committing set ( Definition 3.1 ) and on the dual notion of non-committing set ( Definition 3.3 below). Well-formedness is formally defined in Definition 3.4 by requiring the committing and non-committing sets to be disjoint. Definition 3.3 (Non-committing set). Let \mathtt{G} be an initial global type, and let c be a MC definition in \mathtt{G} , and {\mathtt{q}\rightarrowtriangle\mathtt{p}:\,{\color[rgb]{0,0,1}S_{1}}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:\,{\color[rgb]{0,0,1}S_{2}}} be the outermost occurrence of c in \mathtt{U}(\mathtt{G}) . The non-committing set of c in \mathtt{G} , denoted \Uparrow^{c}\hskip-2.84526pt(\mathtt{G}) , is defined as follows, relying on auxiliary function \Uparrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C}) : \begin{array}[]{l}\Uparrow^{c}\hskip-2.84526pt(\mathtt{G})\penalty\ \coloneq\penalty\ \bigcup_{G\in\mathtt{types}({\color[rgb]{0,0,1}S_{1}})}\Uparrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}\{\mathtt{p}\}})\penalty\ \cup\penalty\ \bigcup_{G\in\mathtt{types}({\color[rgb]{0,0,1}S_{2}})}\Uparrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}\{\mathtt{p},\mathtt{q}\}})\end{array} In contrast to \Downarrow^{c}\hskip-2.84526pt(\mathtt{G}) in Definition 3.1 , \Uparrow^{c}\hskip-2.84526pt(\mathtt{G}) does not include \mathtt{labels}({\color[rgb]{0,0,1}S_{1}})\cup\mathtt{labels}({\color[rgb]{0,0,1}S_{2}}) in the non-committing set of c . Function \Uparrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}C}) is defined like \Downarrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}C}) from Definition 3.1 except the case for interaction types that is dual: specifically, \Uparrow^{c}\hskip-2.84526pt(\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S},{\color[rgb]{0.5,0.5,0.5}C}) returns \Uparrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C\cup\{\mathtt{q}\}}) if (\mathtt{p}\in C\penalty\ \land\penalty\ \mathtt{q}\not\in C) , and returns \mathtt{labels}({\color[rgb]{0,0,1}S})\penalty\ \cup\penalty\ \bigcup_{\mathtt{G}\in\mathtt{types}({\color[rgb]{0,0,1}S})}\Uparrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C}) otherwise. Definition 3.4 (Well-formedness). Initial \mathtt{G} is well-formed if for all c in \mathtt{G} , \Uparrow^{c}\hskip-2.84526pt(\mathtt{G}){}{}\,\cap\Downarrow^{c}\hskip-2.84526pt(\mathtt{G}){}{}=\emptyset . Since the syntactic structure of \mathtt{U}(\mathtt{G}) is finite, well-formedness yields a decidable algorithm based on the definitions of committing and non-committing sets. Hereafter we assume all initial global types to be well-formed. Example 3.5 (Well-formedness). One can verify that the global type \mathtt{G}_{\textrm{✗}} in ( 2 ) is not well-formed by observing that b\in\penalty\ \Uparrow^{c}\hskip-2.84526pt(\mathtt{G}_{\textrm{✗}}){}{} and b\in\penalty\ \Downarrow^{c}\hskip-2.84526pt(\mathtt{G}_{\textrm{✗}}){}{} . One can verify that \mathtt{G}_{\textrm{✓}} below is well-formed by observing that \Downarrow^{c}\hskip-2.84526pt(\mathtt{G}_{\textrm{✓}}){}{}=\{a,d,e\} , \Uparrow^{c}\hskip-2.84526pt(\mathtt{G}_{\textrm{✓}}){}{}=\{b\} , and \{a,d,e\}\cap\{b\}=\emptyset . \begin{array}[]{llll}\mathtt{G}_{\textrm{✓}}&=&\mu\mathtt{t}.\,(\mathtt{q}\rightarrowtriangle\mathtt{p}:{\color[rgb]{0,0,0}a}.\,\mathtt{q}\rightarrowtriangle\mathtt{r}:{\color[rgb]{0,0,0}b}.\,\mathtt{t}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\,\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,0}d}.\mathtt{p}\rightarrowtriangle\mathtt{r}:{\color[rgb]{0,0,0}e}.\,\mathtt{t})\\ \mathtt{U}(\mathtt{G}_{\textrm{✓}})&=&\mathtt{q}\rightarrowtriangle\mathtt{p}:{\color[rgb]{0,0,0}a}.\,\,\mathtt{q}\rightarrowtriangle\mathtt{r}:{\color[rgb]{1,0,0}b}.\,{\mathtt{G}_{\textrm{✓}}}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,0}d}.\,\mathtt{p}\rightarrowtriangle\mathtt{r}:{\color[rgb]{0,0,0}e}.\,{\color[rgb]{0,0,1}\mu\mathtt{t}.\,(\mathtt{q}\rightarrowtriangle\mathtt{p}:a.\,\mathtt{q}\rightarrowtriangle\mathtt{r}:{\color[rgb]{1,0,0}b}.\,\mathtt{t}}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\color[rgb]{0,0,1}\ldots)\end{array} This example is noteworthy: label b occurs multiple times in \mathtt{U}(\mathtt{G}_{\textrm{✓}}) but all occurrences are consistent as they are all non-committing. The occurrence of b on the RHS of the outer c is non-committing because the receiver \mathtt{r} is already committed to that block, having previously received committing label e . 3.2. Semantics of Global Types The semantics of global types is defined as a Labelled Transition System over terms \mathtt{G} with labels \ell:=\mathtt{p}\mathtt{q}!a\mid\mathtt{p}\mathtt{q}?a\mid\nu c \mathtt{p}\mathtt{q}!a (resp. \mathtt{p}\mathtt{q}?a ) denotes the sending (resp. receiving) action of message a from \mathtt{p} to \mathtt{q} . Label \nu c is for MC instantiation. We define the subject of a label as the singleton set containing the role performing the action described by that label: \mathtt{sbj}(\mathtt{p}\mathtt{q}!a)=\mathtt{sbj}(\mathtt{q}\mathtt{p}?a)=\{\mathtt{p}\} . In what follows, we may write \mathtt{p} as a shorthand for the singleton \{\mathtt{p}\} . The subject \nu c is defined to be the empty set. In the LTS we assume knowledge of the original initial (or base ) global type from which a given state is reached. We denote it with \underline{\mathtt{G}} . This is akin to assuming knowledge of the original static protocol specification of an ongoing session. The rules for the LTS are given in Figure 4 . The first set of rules for interactions is given in Figure 4 (top), and is a minor adaptation of the semantics in ( 27 ) . The remaining rules are new for MC. \mathtt{[Inst]} instantiates a MC. \mathtt{[Ctx1]} and \mathtt{[Ctx2]} handle nested instantiations. The conditions on the roles ensure that once a side is resolved (i.e., no role can act in it anymore), it cannot perform degenerate \nu c transitions that would artificially break our correspondence results ( Section 4.3 ). In \mathtt{[Ctx1]} , \mathtt{G}_{l} is resolved when all roles are committed to the right. In \mathtt{[Ctx2]} , \mathtt{G}_{r} is resolved when some roles commit to the left. The asymmetry in the conditions of \mathtt{[Ctx1]} and \mathtt{[Ctx2]} reflects the fact that commitment to the RHS does not immediately preclude actions on the LHS, until all participants have committed. Maintaining the MC contexts, including the resolved sides in the global types (which will be incorporated into the projected local types), is important for correctly characterising stale messages in the projected systems, and thus for ensuring our correspondence results. \mathtt{[LSnd]} allows a send action by the LHS if the subject \mathtt{p} is not committed to the RHS. \mathtt{[RSnd]} is symmetric, except \mathtt{p} is added to \mathcal{R} (any action on the RHS is committing). Rules \mathtt{[LRcv1]} and \mathtt{[LRcv2]} are for committing and non-committing receive actions on the LHS, respectively. In both cases, the subject \mathtt{q} must not be committed on the RHS. \mathtt{[RRcv]} is similar for receive actions in the RHS. \begin{array}[]{cc}\begin{array}[]{cc}\mathtt{p}\rightarrowtriangle\mathtt{q}:\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a_{k}}}\penalty\ \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ \penalty\ \penalty\ (k\in I)\penalty\ \penalty\ \mathtt{[Snd]}\\[8.5359pt] \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a_{k}}}\penalty\ \mathtt{G}_{k}\penalty\ \penalty\ \penalty\ \mathtt{[Rcv]}\penalty\ \penalty\ \penalty\ \hskip 18.49988pt\frac{\forall i\in I\hskip 16.09991pt\mathtt{G}_{i}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \mathtt{G}^{\prime}_{i}\hskip 16.09991pt\mathtt{p},\mathtt{q}\not\in\mathtt{sbj}(\ell)}{\mathtt{p}\rightarrowtriangle\mathtt{q}:\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \mathtt{p}\rightarrowtriangle\mathtt{q}:\{a_{i}.\mathtt{G}^{\prime}_{i}\}_{i\in I}}\penalty\ \penalty\ \mathtt{[Cont1]}\\[19.91684pt] \frac{\mathtt{G}[\mu\mathtt{t}.\mathtt{G}/\mathtt{t}]\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ {\mathtt{G}^{\prime}}}{\mu\mathtt{t}.\mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ {\mathtt{G}^{\prime}}}\penalty\ \penalty\ \mathtt{[Rec]}\hskip 18.49988pt\penalty\ \penalty\ \frac{\mathtt{G}_{k}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ {\mathtt{G}^{\prime}_{k}}\hskip 16.09991pt\mathtt{q}\not\in\mathtt{sbj}(\ell)\hskip 16.09991pt\forall i\in I\setminus k.\,\mathtt{G}_{i}=\mathtt{G}_{i}^{\prime}}{\mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\{a_{i}.\mathtt{G}^{\prime}_{i}\}_{i\in I}}\penalty\ \penalty\ \mathtt{[Cont2]}\\[19.91684pt] \hline\cr\\ \end{array}\\ \begin{array}[]{rr}{\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{G}_{2}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}\penalty\ {\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c}_{\emptyset,\emptyset}\color[rgb]{0,0,0}\mathtt{G}_{2}}}\penalty\ \penalty\ \mathtt{[Inst]}&\frac{\mathtt{G}_{l}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}\penalty\ {\mathtt{G}_{l}^{\prime}}\hskip 8.04996pt\mathtt{R}(\underline{\mathtt{G}})\neq\mathcal{R}}{\mathtt{G}=\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}\penalty\ {\mathtt{G}^{\prime}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}}}\penalty\ \penalty\ \mathtt{[Ctx1]}\\[19.91684pt] \frac{\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}\penalty\ {\mathtt{G}_{r}^{\prime}}\hskip 8.04996pt\mathcal{L}=\emptyset}{\mathtt{G}=\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{\penalty\ }_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}\penalty\ {\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{\penalty\ }_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}^{\prime}}}\penalty\ \penalty\ \mathtt{[Ctx2]}&\frac{\mathtt{G}_{l}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ {\mathtt{G}_{l}^{\prime}}\hskip 8.04996pt\color[rgb]{0.5,0.5,0}\mathtt{p}\not\in\mathcal{R}}{\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ {\mathtt{G}^{\prime}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}}}\penalty\ \penalty\ \mathtt{[LSnd]}\\[22.76228pt] \frac{\mathtt{G}_{l}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ {\mathtt{G}_{l}^{\prime}}\hskip 16.09991pt\color[rgb]{0.5,0.5,0}\mathtt{q}\not\in\mathcal{R}\hskip 16.09991pta\in\Downarrow^{c}\hskip-2.84526pt(\underline{\mathtt{G}})}{\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ {\mathtt{G}^{\prime}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c}_{\mathcal{L}\cup\{\mathtt{q}\},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}}}\penalty\ \penalty\ \mathtt{[LRcv1]}&\frac{\mathtt{G}_{l}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ {\mathtt{G}_{l}^{\prime}}\hskip 16.09991pt\color[rgb]{0.5,0.5,0}\mathtt{q}\not\in\mathcal{R}\hskip 16.09991pta\not\in\Downarrow^{c}\hskip-2.84526pt(\underline{\mathtt{G}})}{\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ {\mathtt{G}^{\prime}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}}}\penalty\ \penalty\ \mathtt{[LRcv2]}\\[25.6073pt] \frac{\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ {\mathtt{G}_{r}^{\prime}}\hskip 16.09991pt\color[rgb]{0.5,0.5,0}\mathtt{p}\not\in\mathcal{L}}{\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ {\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}\cup\{\mathtt{p}\}}\color[rgb]{0,0,0}\mathtt{G}^{\prime}_{r}}}\penalty\ \penalty\ \mathtt{[RSnd]}&\frac{\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ {\mathtt{G}_{r}^{\prime}}\hskip 16.09991pt\color[rgb]{0.5,0.5,0}\mathtt{q}\not\in\mathcal{L}}{\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{r}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ {\mathtt{G}_{l}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}\cup\{\mathtt{q}\}}\color[rgb]{0,0,0}\mathtt{G}^{\prime}_{r}}}\penalty\ \penalty\ \mathtt{[RRcv]}\end{array}\end{array} Figure 4. Global semantics: standard rules (top) and new rules for MC (bottom) Let \vv\ell=\ell_{0},\ldots,\ell_{n} be a (possibly empty) vector. We write \mathtt{G}_{0}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\vv\ell}}\penalty\ \mathtt{G}_{n+1} if \forall i\in{0,\ldots,n}.\,\mathtt{G}_{i}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell_{i+1}}}\penalty\ \mathtt{G}_{i+1} , (or simply \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }\hskip-3.44444pt^{*}}\penalty\ {}\mathtt{G}^{\prime} when labels are irrelevant). We say \mathtt{G}^{\prime} is reachable from \mathtt{G} if \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }\hskip-3.44444pt^{*}}\penalty\ {}\mathtt{G}^{\prime} . We just say \mathtt{G}^{\prime} is reachable if it is reachable from an initial global type. Labels or reached states may be omitted. The LTS for global types has a monotonicity property: the sets \mathcal{L} and \mathcal{R} of a MC are monotonically non-decreasing with respect to transition. Example 3.6 (Global MC steps). One way a well-formed MC may proceed is shown below. In the second line, assume \mathtt{G}_{1}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }\hskip-3.44444pt^{*}}\penalty\ {}\mathtt{G}_{1}^{\prime} on the LHS where observer \mathtt{p} is not the subject in any of those steps. \begin{array}[]{lll}\mathtt{q}\mathbin{\rightarrowtriangle}\mathtt{p}:a_{1}.\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{p}\mathbin{\rightarrowtriangle}\mathtt{q}:a_{2}.\mathtt{G}_{2}&\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}&\mathtt{q}\mathbin{\rightarrowtriangle}\mathtt{p}:a_{1}.\mathtt{G}_{1}\blacktriangleright_{\emptyset,\emptyset}^{c}\mathtt{p}\mathbin{\rightarrowtriangle}\mathtt{q}:a_{2}.\mathtt{G}_{2}\\ &\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }\hskip-3.44444pt^{*}}&\mathtt{q}\mathbin{\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}}\mathtt{p}:a_{1}\{a_{1}.\mathtt{G}_{1}^{\prime}\}\blacktriangleright_{\emptyset,\emptyset}^{c}\mathtt{p}\mathbin{\rightarrowtriangle}\mathtt{q}:a_{2}.\mathtt{G}_{2}\quad(*)\\ \end{array} The marked state may then proceed one of two ways. In the upper of the paths below, observer \mathtt{p} also commits to the LHS, followed by \mathtt{q} and other roles after some more steps. (*) \mathtt{G}_{1}^{\prime}\blacktriangleright_{\{\mathtt{p}\},\emptyset}^{c}{\color[rgb]{0.5,0.5,0.5}\mathtt{p}\mathbin{\rightarrowtriangle}\mathtt{q}:a_{2}.\mathtt{G}_{2}} \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }\hskip-3.44444pt^{*}}\penalty\ {}\penalty\ \mathtt{G}_{1}^{\prime\prime}\blacktriangleright_{\{\mathtt{p},\mathtt{q},...\},\emptyset}^{c}{\color[rgb]{0.5,0.5,0.5}\mathtt{p}\mathbin{\rightarrowtriangle}\mathtt{q}:a_{2}.\mathtt{G}_{2}} \mathtt{q}\mathbin{\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}}\mathtt{p}:a_{1}\{a_{1}.\mathtt{G}_{1}^{\prime}\}\blacktriangleright_{\emptyset,\{\mathtt{p}\}}^{c}\mathtt{p}\mathbin{\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}}\mathtt{q}:a_{2}\{a_{2}.\mathtt{G}_{2}^{\prime}\}\penalty\ \penalty\ \penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }\hskip-3.44444pt^{*}}\penalty\ {}\penalty\ {\color[rgb]{0.5,0.5,0.5}\mathtt{q}\mathbin{\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}}\mathtt{p}:a_{1}\{a_{1}.\mathtt{G}_{1}^{\prime\prime\prime}\}}\blacktriangleright_{\emptyset,\{\mathtt{p},\mathtt{q},\ldots\}}^{c}\mathtt{G}_{2}^{\prime\prime} \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{q}\mathtt{p}?a_{1}}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a_{2}}}\penalty\ The lower path corresponds to the race condition situation where \mathtt{q} instead commits on the RHS, leading to a (transient) period with active interactions (e.g., \mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}} ) by roles on both sides of the MC. However, assuming that all roles have appropriate inputs on the RHS by which they can learn of \mathtt{q} ’s decision (such as the a_{1} input by \mathtt{p} ), they will eventually follow the observer into committing on the RHS and no further actions will occur on the LHS. The conditions for ensuring safe eventual commitment by all roles are formalised in the next subsection. 3.3. Progress of Global Types Progress ensures that any role \mathtt{p}\in\mathtt{R}(\mathtt{G}) either (1) can make a move (immediately or after actions by other roles) or (2) is in a final state. Intuitively, this means that no role is permanently stuck. The notion of final state is captured syntactically by \mathtt{R}(\mathtt{G}) : if \mathtt{r}\in\mathtt{R}(\mathtt{G}) then \mathtt{r} is not in a final state (i.e., it is still active in \mathtt{G} ). Recall that \mathtt{R}(\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2})=\mathtt{R}(\mathtt{G}_{1})\setminus\mathcal{R}\penalty\ \cup\penalty\ \mathtt{R}(\mathtt{G}_{2})\setminus\mathcal{L} and hence, once a role is committed to one block, it is not active in the other block. For example, both \mathtt{p} and \mathtt{q} are in a final state in \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:\{a.\mathtt{end}\}\,\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\emptyset,\{\mathtt{p},\mathtt{q}\}}\color[rgb]{0,0,0}\mathtt{end} . Definition 3.7 (Progress). \mathtt{G} enjoys progress if for all \mathtt{G}^{\prime} reachable from \mathtt{G} the following holds: \mathtt{r}\in\mathtt{R}(\mathtt{G}^{\prime})\quad\Rightarrow\quad\mathtt{G}^{\prime}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{}\hskip-3.44444pt^{*}}\penalty\ \hskip-5.69046pt\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \penalty\ \text{ with }\penalty\ \mathtt{sbj}(\ell)=\mathtt{r} As standard in MST ( 30 ; 22 ) , not all global types enjoy progress. We give two sufficient 3 3 3 Complete decidable conditions are, unfortunately, not possible ( 29 ) . conditions for progress: awareness and balance . Awareness guarantees that each role eventually commits when the RHS is taken, and that each role with a terminating execution commits when the LHS is taken. Awareness builds on two relations over roles ( Definition 3.8 ). Definition 3.8 (Role dependencies <_{\mathtt{G}} and \ll_{\mathtt{G}} ). Let \mathtt{p},\mathtt{q}\in\mathtt{R}(\mathtt{G}) . We define two kinds of dependencies between roles: strict dependence , written \mathtt{p}<_{\mathtt{G}}\mathtt{q} , and eventual dependence , written \mathtt{p}\ll_{\mathtt{G}}\mathtt{q} . • \mathtt{p}<_{\mathtt{G}}\mathtt{q} , if \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\vec{\ell}\,\ell_{\mathtt{q}}}}\penalty\ \penalty\ \land\penalty\ \mathtt{sbj}(\ell_{\mathtt{q}})=\mathtt{q} implies \exists{\ell}\in\vec{\ell}.\penalty\ \mathtt{sbj}(\ell)=\mathtt{p} • \mathtt{p}\ll_{\mathtt{G}}\mathtt{q} , if \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\vec{\ell}}}\penalty\ \mathtt{G}^{\prime} implies \exists a.\penalty\ \mathtt{p}\mathtt{q}!a\in\vec{\ell}\penalty\ \lor\penalty\ \mathtt{G}^{\prime}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{}\hskip-3.44444pt^{*}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ Namely: \mathtt{p}<_{\mathtt{G}}\mathtt{q} if \mathtt{q} will only take action after \mathtt{p} does, and \mathtt{p}\ll_{\mathtt{G}}\mathtt{q} if it is always possible for \mathtt{p} to send a message to \mathtt{q} . We say that \mathtt{p} diverges in \mathtt{G} if \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{}\hskip-3.44444pt^{*}}\penalty\ \mathtt{G}^{\prime} implies \mathtt{G}^{\prime}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{}\hskip-3.44444pt^{*}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ with \mathtt{sbj}(\ell)=\mathtt{p} . Definition 3.9 (Awareness). An active MC \mathtt{G}=\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{\mathtt{p}}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2} is aware if for all \mathtt{r}\in\mathtt{R}(\mathtt{G})\setminus\mathtt{p} : (1) \penalty\ \mathcal{R}=\emptyset\penalty\ \Longrightarrow\penalty\ \mathtt{p}<_{\mathtt{G}_{2}}\mathtt{r} (single-decision), (2) \penalty\ \mathcal{L}=\emptyset\penalty\ \Longrightarrow\penalty\ \mathtt{p}\ll_{\mathtt{G}_{1}}\mathtt{r} or \mathtt{r} diverges in \mathtt{G}_{1} (clear-termination). Similarly, an MC definition \mathtt{G}=\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{\mathtt{p}}\mkern 1.0mu}\mathtt{G}_{2} is aware if for all \mathtt{r}\in\mathtt{R}(\mathtt{G}) , \mathtt{p}<_{\mathtt{G}_{2}}\mathtt{r} and \mathtt{p}\ll_{\mathtt{G}_{1}}\mathtt{r} . A global type \mathtt{G} is aware if all MC definitions and active MC in \mathtt{U}(\mathtt{G}) are aware. Single-decision requires that, on the RHS, all roles depend on the observer until committed. Clear termination allows the roles to start communicating on the LHS without waiting for a committing message. However, if their execution terminates, they must receive a committing message; this is key to progress, as illustrated below in Example 3.10 . The use of \mathtt{U}(\mathtt{G}) is necessary to deal with label capture (as shown in Example 3.2 ). Example 3.10 (Clear termination). In the type below (left): if observer \mathtt{p} receives a and terminates, then \mathtt{q} is unable to locally determine whether to terminate or continue waiting for a b that will never arrive (i.e., termination is not clear ); one fix is to add \mathtt{p}\rightarrowtriangle\mathtt{q}:c on the LHS. As a generalisation, however we can safely lift eventual dependency for infinite executions, as shown in a stream exception pattern below (right) where \mathtt{q} establishes a communication (label c ) and immediately starts the stream, and potentially handle later a connection failure message ( b by \mathtt{p} ): \mathtt{q}\rightarrowtriangle\mathtt{p}:a.\penalty\ \mathtt{end}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:b.\penalty\ \mathtt{end}\penalty\ \penalty\ {\color[rgb]{1,0,0}\textrm{✗}}\qquad\mathtt{q}\rightarrowtriangle\mathtt{p}:c.\,\mu\mathtt{t}.(\mathtt{q}\rightarrowtriangle\mathtt{p}:a.\penalty\ \mathtt{t})\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:b.\penalty\ \mathtt{end}\penalty\ \penalty\ {\color[rgb]{0,1,0}\textrm{✓}} Consider now a third-party exception below, where a ‘third-party’ observer \mathtt{r} may decide, after some interactions between \mathtt{p} and \mathtt{q} , to either commit on the LHS or raise the RHS exception: \mathtt{q}\rightarrowtriangle\mathtt{r}:c.\,\mu\mathtt{t}.(\mathtt{q}\rightarrowtriangle\mathtt{p}:a.\penalty\ \mathtt{t})\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathtt{r}\rightarrowtriangle\mathtt{q}:b.\,\mathtt{r}\rightarrowtriangle\mathtt{p}:b.\penalty\ \mathtt{end}\penalty\ \penalty\ {\color[rgb]{0,1,0}\textrm{✓}} Clear-termination holds because: (i) \mathtt{r} is able to commit to the LHS by receiving c , (ii) all other roles ( \mathtt{p} , \mathtt{q} ) do not need to commit because they diverge within the LHS. Example 3.11 (Interrupt pattern). Interrupts can be modelled with a minor extension to the theory (implemented in Section 5.2 ), if we allow the observer to interact on the LHS before committing on that side. To this aim, allocate a set {\color[rgb]{1,0,0}D} of choice labels used by observers to commit on the LHS . The interrupt pattern can then be expressed as the global type below, letting {\color[rgb]{1,0,0}d}\in{\color[rgb]{1,0,0}D} and a,b,c\not\in{\color[rgb]{1,0,0}D} : \mathtt{q}\rightarrowtriangle\mathtt{p}:c.\,\mu\mathtt{t}.(\mathtt{q}\rightarrowtriangle\mathtt{p}:\{a.\penalty\ \mathtt{t},\,{\color[rgb]{1,0,0}d}.\,\mathtt{p}\rightarrowtriangle\mathtt{q}:e.\,\mathtt{end}\})\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:b.\penalty\ \mathtt{end} Unlike in the stream exception (Example 3.10 ), now \mathtt{p} can repeatedly receive messages a from \mathtt{q} before, possibly, throwing the interrupt b (or committing/terminating on the LHS). Our theory can be easily adapted to support interrupt patterns using {\color[rgb]{1,0,0}D} by: (1) updating the definition of committing set so that the committing chains on the LHS start with actions in {\color[rgb]{1,0,0}D} (see Section C.1 ), (2) adjusting the existential quantifier in Definition 3.8 (eventual dependence \ll_{\mathtt{G}} ) by requiring label a to be in {\color[rgb]{1,0,0}D} (i.e., \exists{a}\in{\color[rgb]{1,0,0}D} ). Awareness ensures convergence of the roles in a block by requiring dependencies with the observer. However, if a role does not appear in some execution branches, it may not be able to converge with the observer’s decision. This is a known problem also with branching choices: (3) \mathtt{p}\rightarrowtriangle\mathtt{q}:\{a.\,\mathtt{q}\rightarrowtriangle\mathtt{r}:\{c.\mathtt{end}\},\penalty\ b.\,\mathtt{q}\rightarrowtriangle\mathtt{p}:\{c.\mathtt{end}\}\} In ( 3 ), role \mathtt{r} does not know whether to terminate or wait for a message, and thus does not terminate. Balance ( Definition 3.12 ) generalizes this idea to MC, operating on the unfolding \mathtt{U}(\mathtt{G}) to account for label capture. Definition 3.12 also uses a truncation operator \mathtt{Trunc}(\mathtt{G}) that replaces each recursive subterm in \mathtt{G} with \mathtt{end} . Assuming \mathtt{G} has no free recursion variables: \mathtt{Trunc}(\mu\mathtt{t}.\mathtt{G}^{\prime})=\mathtt{Trunc}(\mathtt{end})=\mathtt{end} . All other cases are defined inductively. Truncation prevents expressiveness loss: Definition 3.12 universally quantifies over subterms of \mathtt{U}(\mathtt{G}) which would consider recursive subterms out of their intended context. For example, without truncation any instantiation of example ( 1 ) in Section 3.1 would (unnecessarily) be excluded as unbalanced. Definition 3.12 (Balance). A global type \mathtt{G} is balanced if for all subterms \mathtt{G}^{\prime} of \mathtt{Trunc}(\mathtt{U}(\mathtt{G})) : (1) \mathtt{G}^{\prime}=\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S}\penalty\ \penalty\ \Rightarrow\penalty\ \penalty\ \forall\mathtt{G}_{1},\mathtt{G}_{2}\in\mathtt{types}({\color[rgb]{0,0,1}S}),\penalty\ \penalty\ \mathtt{R}(\mathtt{G}_{1})\setminus\{\mathtt{p},\mathtt{q}\}=\mathtt{R}(\mathtt{G}_{2})\setminus\{\mathtt{p},\mathtt{q}\} (2) \mathtt{G}^{\prime}=\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{\penalty\ }\mkern 1.0mu}\mathtt{G}_{2}\penalty\ \penalty\ \Rightarrow\penalty\ \penalty\ \mathtt{R}(\mathtt{G}_{1})=\mathtt{R}(\mathtt{G}_{2}) (3) \mathtt{G}^{\prime}=\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{\penalty\ }_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2}\penalty\ \penalty\ \Rightarrow\penalty\ \penalty\ \mathtt{R}(\mathtt{G}_{1})\cup\mathcal{L}=\mathtt{R}(\mathtt{G}_{2})\cup\mathcal{R} Case (3) allows committed roles to ‘disappear’ from a block. Case (1) is normally entailed by projection. We give it here for a simpler presentation and separation of concerns. Theorem 3.13 (Progress). If \mathtt{G} is initial, aware, and balanced then it enjoys progress . The proof relies on a coherence property: all the committed roles are committed to the same side. Formally, if \mathtt{G}=\mathbf{C}[\,\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2}\,] then \mathcal{L}=\emptyset\,\lor\,\mathcal{R}=\emptyset . Essentially, we prove that (1) awareness, balance, and coherence are preserved by transition, and (2) balanced, aware, and coherent global types enjoy progress. Theorem 3.13 follows since initial global types are always coherent. See Section D.8 for details of the proofs. 4. Local Types The syntax of local types is given by the following grammar: \mathtt{L}::=\mathtt{\mathtt{p}}\mathop{\&_{i\in I}}a_{i}.\mathtt{L}_{i}\penalty\ \mid\penalty\ \mathtt{\mathtt{p}}\mathop{\oplus_{i\in I}}a_{i}.\mathtt{L}_{i}\penalty\ \mid\penalty\ \mu\mathtt{t}.\mathtt{L}\penalty\ \mid\penalty\ \mathtt{t}\penalty\ \mid\penalty\ \mathtt{end}\penalty\ \mid\penalty\ \mathtt{L}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{L}_{2}\penalty\ \mid\penalty\ \mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\mathtt{L}_{2}\penalty\ \mid\penalty\ \mathtt{L}\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\bullet\penalty\ \mid\penalty\ \bullet\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\mathtt{L} The first five terms are standard; the notation for roles and labels are as in global types. We recall \mathtt{\mathtt{p}}\mathop{\&_{i\in I}}a_{i}.\mathtt{L}_{i} is a branching type, waiting for one of the labels \{a_{i}\}_{i\in I} and continuing as the corresponding \mathtt{L}_{i} . Term \mathtt{\mathtt{p}}\mathop{\oplus_{i\in I}}a_{i}.\mathtt{L}_{i} is the corresponding send/selection type. We often omit \mathtt{end} . Terms \mathtt{L}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{L}_{2} and \mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\mathtt{L}_{2} are for MC definition and active MC , respectively. The terms \mathtt{L}\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\bullet and \bullet\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\mathtt{L} model run-time states in which the role has committed on the LHS or the RHS, respectively. We omit the annotation c when it is clear from context or not relevant. In-transit/buffered (i.e., yet to be consumed) messages are modelled using FIFO queues. The localised view of a global type for a given role is thus a configuration (\mathtt{p},\mathtt{L},\sigma) where \mathtt{p} is the role, \mathtt{L} is the local type specifying the behaviour of \mathtt{p} , and \sigma is a local FIFO queue of messages that have been sent to \mathtt{p} (and possibly arrived) but not consumed. A global type therefore corresponds overall to a collection of local configurations. We call this collection a system , ranged over by Y,Y^{\prime} . \begin{array}[]{llll}Y::=(\mathtt{p}_{i},\mathtt{L}_{i},\sigma_{i})_{i\in I}&\sigma:\mathtt{q}\mapsto\vv{m}&m::=(a,\,\pi)&\pi::=\epsilon\;|\;\texttt{l}.\pi\;|\;\texttt{r}.\pi\end{array} We assume the configurations of a system have pairwise-distinct roles. Messages carry a path \pi , which fully qualifies the active MC context under which the message was sent. A path specifies left-to-right the top-most MC to the inner MC of the sending local type. We often omit the trailing \epsilon . As an example, (\mathtt{L}_{1}\blacktriangleright{\color[rgb]{1,0,1}\mathtt{p}\oplus a})\blacktriangleright{\color[rgb]{1,0,1}\mathtt{p}\oplus b} may send two messages: (a,\,\texttt{l}.\texttt{r}) and (b,\texttt{r}) . In global types, the equivalent path information is implicit in the global type context (nested active MCs) in which the corresponding in-transit message term ( \mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}} ) occurs. 4.1. Operational Semantics The local operational semantics uses the labels below and two main judgments: \begin{array}[]{c}\ell::=\mathtt{p}\mathtt{q}!a\;|\;\mathtt{p}\mathtt{q}?a\;|\;\nu c\;|\;\rho\qquad Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime}\qquad\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime}\end{array} Labels \ell now include \rho for stale message purging from local queues. The first judgment Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime} is for top-level concurrent execution of systems. It has just three rules. \begin{array}[]{c}\frac{{Y}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime\prime}}{Y,Y^{\prime}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime\prime},Y^{\prime}}\hskip 9.24994pt\textsc{Right={[Par]}}\hskip 18.49988pt\hskip 18.49988pt\hskip 9.24994pt\frac{\mathsf{gc}(\mathtt{L},\sigma)=\sigma^{\prime}}{(\mathtt{p},\mathtt{L},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\rho}}\penalty\ (\mathtt{p},\mathtt{L},\sigma^{\prime})}\hskip 9.24994pt\textsc{Right={[Discard]}}\hskip 18.49988pt\hskip 18.49988pt\hskip 18.49988pt\frac{\color[rgb]{0.5,0.5,0.5}\epsilon:\color[rgb]{0,0,0}Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime}}{Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime}}\hskip 9.24994pt\textsc{Right={[Low]}}\end{array} Rule [Par] is a structural rule that models concurrent execution. Rule [Low] uses lower-level judgments of the form \color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime} (see below). Rule [Discard] performs stale message purging on the local queue \sigma of a configuration. This is necessary to maintain correspondence between the executions of global and local types. Consider the example in ( 4 ) where the right-hand side term is reached after the following sequence of actions: (1) \mathtt{q} sends c to \mathtt{p} and commits to the RHS, (2) \mathtt{p} sends a to \mathtt{q} (on the LHS), (3) \mathtt{p} receives c and commits to the RHS, (3) \mathtt{p} sends d to \mathtt{q} on the RHS. (4) Y,(\mathtt{q},\,\mathtt{p}\&a.\mathtt{p}\oplus b.\mathtt{end}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{p}\oplus c.\mathtt{p}\&d.\mathtt{end},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{}\hskip-3.44444pt^{*}}\penalty\ Y^{\prime},(\mathtt{q},\,\bullet\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{p}\&d.\mathtt{end},\sigma:\mathtt{p}\mapsto(a,\texttt{l}),(d,\texttt{r})) In the reached term – on the right-hand side of ( 4 ) – the enqueued message (a,\texttt{l}) pertains to the LHS of the MC and is essentially garbage. The presence of (a,\texttt{l}) in \mathtt{q} ’s queue would naively break correspondence ( Section 4.3 ) with the projection of the corresponding metatheoretical global type \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:a.\mathtt{q}\rightarrowtriangle\mathtt{p}:b.\mathtt{end}\blacktriangleright_{\emptyset,\{\mathtt{p},\mathtt{q}\}}\mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:\,d.\mathtt{end} . Fortunately, local types allow us to define a purge function \mathsf{gc} that operates solely on information that is local to the configuration. In the general case of nested MC, we identify stale messages by traversing the MC structures of the receiver’s local type \mathtt{L} using the sender’s path \pi included in the message. This check is defined inductively as a predicate \mathtt{stale}(\pi,\mathtt{L}) , which returns true if following \pi in \mathtt{L} hits a stale ( \bullet ) side. Below, the otherwise cases may include non-initialized MC which are never stale as still uncommitted, and \mathtt{stale}(\epsilon,\mathtt{L})=\mathtt{false} for all \mathtt{L} . \begin{array}[]{llcll}\begin{array}[]{llcll}\mathtt{stale}(\texttt{l}.\pi,\mathtt{L})=\begin{cases}\mathtt{true}&\mathtt{L}=\bullet\blacktriangleright\mathtt{L}_{2}\\ \mathtt{stale}(\pi,\mathtt{L}_{1})&\mathtt{L}=\mathtt{L}_{1}\blacktriangleright\mathtt{L}_{2}\textit{ or }\\ &\penalty\ \mathtt{L}=\mathtt{L}_{1}\blacktriangleright\bullet\\ \mathtt{false}&\textit{otherwise}\end{cases}&&\mathtt{stale}(\texttt{r}.\pi,\mathtt{L})=\begin{cases}\mathtt{true}&\mathtt{L}=\mathtt{L}_{1}\blacktriangleright\bullet\\ \mathtt{stale}(\pi,\mathtt{L}_{2})&\mathtt{L}=\mathtt{L}_{1}\blacktriangleright\mathtt{L}_{2}\textit{ or }\\ &\penalty\ \mathtt{L}=\bullet\blacktriangleright\mathtt{L}_{2}\\ \mathtt{false}&\textit{otherwise}\end{cases}\end{array}\end{array} Purge (a.k.a. garbage collection) \mathsf{gc}(\mathtt{L},\sigma) looks into \sigma (for all \mathtt{p} in its domain) and removes all messages (a,\pi) for which \mathtt{stale}(\pi,\mathtt{L}) is true. Lower-level judgements \pi\vdash Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime} model the main behaviour of configurations. The environment \pi records the MC context for messages being sent. The first three rules in Figure 5 are standard for communications and recursion. Rule [Snd] appends an a_{k} message to the receiver’s queue and continues as \mathtt{L}_{k} . The message is annotated with \pi from the context. Dually, rule [Rcv] consumes the first such message a_{k} annotated by \pi and continues as \mathtt{L}_{k} . [Rec] is standard. The remaining rules are new and define the semantics for MC. [New] instantiates a MC definition. [LSnd] executes an output action in the LHS of an active but not committed MC. The context \pi is updated to \pi.\texttt{l} to indicate the action is happening on the LHS of the current MC. Analogously to global types, sending on the LHS is never committing. For LHS receive actions we have two rules: [LRcv1] (committing) and [LRcv2] (non-committing). As in the global semantics, we infer committing labels from the base \underline{\mathtt{G}} . 4 4 4 Observe that this is purely static information and can be derived (pre-processed) from the source global type. Equivalently, we could embed this information into local types by adding annnotations. [RSnd] is for sending on the RHS which is always committing; likewise [RRcv] for receiving on the RHS (symmetric to [LRcv1] ). See Section E.1 for the full rules, including a structural rule [RCtxt] (which is symmetric to [LCtxt] ), and structural rules [NLCtxt] and [NRCtxt] for \nu c actions on the LHS and RHS of \mathtt{L}_{1}\blacktriangleright\mathtt{L}_{2} , respectively. \begin{array}[]{cr}\frac{k\in I\hskip 16.09991ptm=(a_{k},\,\pi)}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{\mathtt{q}}\mathop{\oplus_{i\in I}}a_{i}.\mathtt{L}_{i},\sigma),(\mathtt{q},\mathtt{L},\sigma^{\prime}[\mathtt{p}\mapsto\vv{m}])\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a_{k}}}\penalty\ (\mathtt{p},\mathtt{L}_{k},\sigma),(\mathtt{q},\mathtt{L},\sigma^{\prime}[\mathtt{p}\mapsto\vv{m}\cdot m])}&{\scriptstyle\textsc{[Snd]}}\\[22.76228pt] \frac{k\in I\hskip 16.09991pt\vv{m}=\vv{m}_{1}\cdot(a_{k},\,\pi)\cdot{\vv{m}}_{2}\hskip 16.09991pt(a,\pi)\not\in\vv{m}_{1}}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{q},\mathtt{\mathtt{p}}\mathop{\&_{i\in I}}a_{i}.\mathtt{L}_{i},\sigma[\mathtt{p}\mapsto\vv{m}])\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a_{k}}}\penalty\ (\mathtt{q},\mathtt{L}_{k},\sigma[\mathtt{p}\mapsto\vv{m}_{1}\cdot{\vv{m}}_{2}])}&{\scriptstyle\textsc{[Rcv]}}\\[17.07182pt] \frac{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}[\mu\mathtt{t}.\mathtt{L}/\mathtt{t}],\sigma),Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime}}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mu\mathtt{t}.\mathtt{L},\sigma),Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime}}\hskip 18.49988pt\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{L}^{\prime},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}\penalty\ (\mathtt{p},\mathtt{L}\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\mathtt{L}^{\prime},\sigma)&{\scriptstyle\textsc{[Rec/New]}}\\[17.07182pt] \frac{{\begin{array}[]{l}\color[rgb]{0.5,0.5,0.5}\pi.\texttt{l}:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}_{1},\sigma),Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime}_{1},\sigma),Y^{\prime}\end{array}}}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma),Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma),Y^{\prime}}\penalty\ \penalty\ \penalty\ \frac{{\begin{array}[]{l}\color[rgb]{0.5,0.5,0.5}\pi.\texttt{r}:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}_{2},\sigma),Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime}_{2},\sigma),Y^{\prime}\end{array}}}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma),Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ (\mathtt{p},\bullet\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}^{\prime}_{2},\sigma),Y^{\prime}}&{\scriptstyle\textsc{[LSnd/RSnd]}}\\ \\ \frac{{\begin{array}[]{l}\color[rgb]{0.5,0.5,0.5}\pi.\texttt{l}:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}_{1},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime}_{1},\sigma^{\prime})\end{array}}\hskip 8.04996pt{\color[rgb]{0.5,0.5,0}a\in\Downarrow^{c}\hskip-2.84526pt(\underline{\mathtt{G}})}}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\bullet,\sigma^{\prime})}\hskip 9.24994pt\frac{{\begin{array}[]{l}\color[rgb]{0.5,0.5,0.5}\pi.\texttt{l}:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}_{1},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime}_{1},\sigma^{\prime})\end{array}}\hskip 8.04996pt{\color[rgb]{0.5,0.5,0}a\not\in\Downarrow^{c}\hskip-2.84526pt(\underline{\mathtt{G}})}}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma^{\prime})}&{\scriptstyle\textsc{[LRcv1/2]}}\\ \\ \frac{{\begin{array}[]{l}\color[rgb]{0.5,0.5,0.5}\pi.\texttt{r}:\color[rgb]{0,0,0}(\mathtt{q},\mathtt{L}_{2},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ (\mathtt{q},\mathtt{L}^{\prime}_{2},\sigma^{\prime})\end{array}}}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{q},\mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma)\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a}}\penalty\ (\mathtt{q},\bullet\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}^{\prime}_{2},\sigma^{\prime})}\hskip 9.24994pt\frac{\color[rgb]{0.5,0.5,0.5}\pi.\texttt{l}:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L},\sigma),Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime},\sigma^{\prime}),Y^{\prime}}{\color[rgb]{0.5,0.5,0.5}\pi:\color[rgb]{0,0,0}(\mathtt{p},\mathtt{L}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\bullet,\sigma),Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ (\mathtt{p},\mathtt{L}^{\prime}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\bullet,\sigma^{\prime}),Y^{\prime}}&{\scriptstyle\textsc{[RRcv/LCtxt]}}\end{array} Figure 5. Local semantics, selected rules. See Section E.1 for omitted structural rules. and the two context rules, [NLCtxt] and [NRCtxt] , for \nu c actions on the LHS and RHS of \mathtt{L}_{1}\blacktriangleright\mathtt{L}_{2} , respectively. 4.2. Projection The distributed counterpart of a global type is a system of configurations derived by projection . The projection of a global type \mathtt{G} onto a role \mathtt{r}\mathop{\in}\mathtt{R}(\mathtt{G}) , written \mathtt{G}\upharpoonright\mathtt{r} , returns a pair (\mathtt{L},\sigma) of a local type and its queue. Recall, the queue \sigma is a mapping from roles \mathtt{r}^{\prime}\in\mathtt{R}(\mathtt{G}) to a vector of messages received, but not consumed, by \mathtt{r} from \mathtt{r}^{\prime} . The main rules for projection, given in Figure 6 , take a context path \pi , which is needed to define messages m being enqueued. Top-level projection \mathtt{G}\mathbin{\upharpoonright}\mathtt{r} is bootstrapped as \color[rgb]{0.5,0.5,0.5}\epsilon\vdash\color[rgb]{0,0,0}\mathtt{G}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0} . \begin{array}[]{l}\color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{\mathtt{p}}\rightarrowtriangle\mathtt{\mathtt{q}}:\{a_{i}:\mathtt{G}_{i}\}_{i\in I}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}=\begin{cases}\mathtt{q}\oplus_{i\in I}a_{i}.\mathtt{L}_{i},\sigma&\text{if }{\mathtt{r}=\mathtt{p}}\hskip 9.24994pt\hskip 9.24994pt\text{where in all cases }\forall i\in I,\,{\color[rgb]{0,0,0}\mathtt{L}_{i},\sigma}=\color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{G}_{i}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\\ \mathtt{p}\&_{i\in I}a_{i}.\mathtt{L}_{i},\sigma&\text{if }{\mathtt{r}=\mathtt{q}}\\ \sqcap_{i\in I}\mathtt{L}_{i},\sigma&\text{if }\mathtt{r}\not\in\{\mathtt{p},\mathtt{q}\}\end{cases}\\[19.91684pt] \color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\,\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}=\begin{cases}\mathtt{L}_{k},\sigma_{k}&\text{if }\mathtt{r}=\mathtt{p}\\ \mathtt{p}\&_{i\in I}a_{i}.\mathtt{L}_{i},\,\sigma_{k}[\mathtt{p}\mapsto(a_{k},\,\pi)\mathop{\cdot}\sigma_{k}(\mathtt{p})]&\text{if }\mathtt{r}=\mathtt{q}\\ \mathtt{L}_{k},\sigma_{k}&\text{if }\mathtt{r}\not\in\{\mathtt{p},\mathtt{q}\}\end{cases}\\ \hskip 122.34692pt\text{where in all cases }\forall i\in I,\,{\color[rgb]{0,0,0}\mathtt{L}_{i},\sigma_{i}}=\color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{G}_{i}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}\text{ and }\forall i\in I\setminus\{k\},\,\sigma_{i}=\sigma_{0}\\[2.84544pt] \color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{G}_{1}\,\mathop{{\color[rgb]{0.75,0,0.25}\triangleright}}\,\mathtt{G}_{2}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}\penalty\ \penalty\ =\penalty\ \penalty\ \mathtt{L}_{1}\,\mathop{{\color[rgb]{0.75,0,0.25}\triangleright}}\,\mathtt{L}_{2},\sigma_{0}\hskip 18.49988pt\text{where }\forall i\in\{1,2\},\,{\color[rgb]{0,0,0}\mathtt{L}_{i},\sigma_{0}}=\color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{G}_{i}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\\[2.84544pt] \color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}=\begin{cases}\mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\bullet,\sigma_{1}&\text{if }\mathtt{r}\mathop{\in}\mathcal{L}\penalty\ \penalty\ \text{ and }\penalty\ \penalty\ {\color[rgb]{0,0,0}\mathtt{L}_{1},\sigma_{1}}=\color[rgb]{0.5,0.5,0.5}\pi.\texttt{l}\vdash\color[rgb]{0,0,0}\mathtt{G}_{1}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\\ \bullet\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma_{2}&\text{if }\mathtt{r}\mathop{\in}\mathcal{R}\penalty\ \penalty\ \text{ and }\penalty\ \penalty\ {\color[rgb]{0,0,0}\mathtt{L}_{2},\sigma_{2}}=\color[rgb]{0.5,0.5,0.5}\pi.\texttt{r}\vdash\color[rgb]{0,0,0}\mathtt{G}_{2}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\\ \mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L}_{2},\sigma_{1}\circ\sigma_{2}&\text{if }\mathtt{r}\mathop{\not\in}\mathcal{L}\mathop{\cup}\mathcal{R}\penalty\ \text{ and }\penalty\ \forall i\in\{1,2\},\,\mathtt{L}_{i},\sigma_{i}=\color[rgb]{0.5,0.5,0.5}\pi_{i}\vdash\color[rgb]{0,0,0}\mathtt{G}_{i}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\\ &\hskip 9.24994pt\text{ with }\penalty\ \pi_{1}=\pi.\texttt{l}\penalty\ \text{ and }\penalty\ \pi_{2}=\pi.\texttt{r}\end{cases}\\[22.76228pt] \begin{array}[]{c}\color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mu\mathtt{t}.\mathtt{G}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}=\begin{cases}\mathtt{end},\sigma_{0}&\penalty\ \text{ if }\mathtt{G}=\mathtt{t}\hskip 113.81102pt\color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{t}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}=\mathtt{t},\sigma_{0}\\ \mathtt{t}^{\prime},\sigma_{0}&\penalty\ \text{ if }\mathtt{G}=\mathtt{t}^{\prime}\land\mathtt{t}^{\prime}\neq\mathtt{t}\hskip 78.24507pt\color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{end}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}=\mathtt{end},\sigma_{0}\\ \mu\mathtt{t}.\mathtt{L},\sigma&\penalty\ \text{ otherwise, with }\color[rgb]{0.5,0.5,0.5}\pi\vdash\color[rgb]{0,0,0}\mathtt{G}\color[rgb]{0,0,1}\upharpoonright\mathtt{r}\color[rgb]{0,0,0}=\mathtt{L},\sigma\end{cases}\end{array}\end{array} Figure 6. Projection of global types to local types and input FIFOs The first two rules for interaction and in-transit messages are standard, except we also project the queues. Notation \sigma_{0} stands for an ‘empty queue’ that maps each \mathtt{p} in its domain to \epsilon . The projection of a message in transit \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\,a_{i}.\mathtt{G}_{i} uses the context \pi to construct the queued message. The case of projection for an active MC, of the form \mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{G}_{2} , uses the operation \sigma_{1}\mathbin{\circ}\sigma_{2} to concatenate queues: if \mathsf{dom}(\sigma_{1})=\mathsf{dom}(\sigma_{2}) then \sigma_{1}\mathbin{\circ}\sigma_{2}=\{\mathtt{r}\mapsto\sigma_{1}(r)\mathop{\cdot}\sigma_{2}(r)\mid\mathtt{r}\mathop{\in}\mathsf{dom}(\sigma_{1})\} . The behaviour of an MC can be considered as starting from the LHS before possibly switching to the RHS, hence the projection accordingly concatenates the LHS and RHS queues in this order. The notation \sqcap_{i\in I}\mathtt{L}_{i} is the standard notion of merge ( 26 ) for projecting onto third-party roles. For example, the projection of \mathtt{p}\rightarrowtriangle\mathtt{q}:\{a_{1}.\,\mathtt{q}\rightarrowtriangle\mathtt{r}:\{a_{1}.\mathtt{end}\},\,a_{2}.\,\mathtt{q}\rightarrowtriangle\mathtt{r}:\{a_{2}.\mathtt{end}\}\} onto \mathtt{r} is defined as \mathtt{p}\&a_{1}.\mathtt{end}\sqcap\mathtt{p}\&a_{2}.\mathtt{end} , yielding \mathtt{p}\&_{i\in\{1,2\}}a_{i}.\mathtt{end} . The definition (omitted) implicitly handles MC in the same way as other non-branching constructs, i.e., the projection of each case must be the same. We extend projection to systems and define the system derived from \mathtt{G} as \mathtt{G}\hskip-2.84526pt\upharpoonright\,=\{(\mathtt{r},\mathtt{L}_{\mathtt{r}},\sigma_{\mathtt{r}})\}_{\mathtt{r}\in\mathtt{R}(\mathtt{G})} where \forall\mathtt{r}\in\mathtt{R}(\mathtt{G})\;.\;\mathtt{L}_{\mathtt{r}},\sigma_{\mathtt{r}}=\mathtt{G}\mathbin{\upharpoonright}\mathtt{r} . 4.3. Operational Correspondence We establish an operational correspondence, called fidelity , between global types and the systems obtained by projection. Fidelity is defined as a weak correspondence relation over pairs of global types and systems, treating \nu c and \rho actions as the silent action \tau . This correspondence is precise, comprising a top-down and a bottom-up property, as depicted below. \mathtt{G} \mathtt{G}^{\prime} Y_{\mathtt{G}} Y Y^{\prime}\color[rgb]{0,0,0}\mathbin{<:}Y_{\mathtt{G}^{\prime}} \upharpoonright \text{(bottom-up)}\hskip 18.49988pt\penalty\ {\color[rgb]{0,0,1}\xrightarrow{{\ell}}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\rho}\hskip-3.09999pt^{*}}\penalty\ \upharpoonright \mathtt{G} Y_{\mathtt{G}} \mathtt{G}^{\prime} Y Y^{\prime}\color[rgb]{0,0,0}<:Y_{\mathtt{G}^{\prime}} \penalty\ {\color[rgb]{0,0,1}\xrightarrow{{\ell}}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\rho}\hskip-3.09999pt^{*}}\penalty\ \upharpoonright \text{(top-down)}\hskip 18.49988pt\penalty\ {\color[rgb]{0,0,1}\xrightarrow{{\ell}}}\penalty\ \upharpoonright Bottom-up fidelity states that each action of a system can be matched with the same action by the corresponding global type, preserving the correspondence given by projection modulo garbage collection and a preorder ‘ <: ’ over local types (discussed below). Top-down fidelity, conversely, states that each step of \mathtt{G} can be matched by a step of Y . The asynchronous nature of mixed choices and the decentralised semantics of systems raise two main challenges: (1) upon commitment of a configuration to a MC block, some messages in its queue may become stale; and (2) localised MC instantiations and recursive unfoldings can cause (a minor form of) misalignment of the configurations. So far, our definitions have paved the way for tackling (1): we use local states \mathtt{L}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\bullet and \bullet\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}\mathtt{L} to keep track of local commitments, and use function \mathsf{gc}() and action \rho to (locally) identify and remove stale messages. Both top-down and bottom-up fidelity may require some number of \rho steps to preserve correspondence. We address (2) using a preorder ‘ <: ’ on pairs of systems, as we now discuss. In a global type, a MC is instantiated with a single “centralised” action \nu c , whereas the local configurations in the derived system independently perform separate decentralised \nu c actions. Decentralised MC instantiation can cause administrative issues for the correspondence. Consider the global types below where \mathtt{G}_{1}=\mathtt{q}\rightarrowtriangle\mathtt{p}:a_{1}.\mathtt{end} and c is instantiated before \mathtt{q} ’s first send action: \begin{array}[]{lll}\mathtt{G}_{P}=\mathtt{q}\rightarrowtriangle\mathtt{r}:b.(\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:a_{2}.\mathtt{end})\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a_{2}}}\penalty\ \mathtt{q}\rightarrowtriangle\mathtt{r}:b.\,(\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{c}_{\emptyset,\{\mathtt{p}\}}\color[rgb]{0,0,0}\mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:2\,a_{2}.\mathtt{end}\,)=\mathtt{G}_{P}^{\prime}\end{array} Consider now configuration Y_{\mathtt{q}} obtained by projecting \mathtt{G}_{P} on \mathtt{q} : Y_{\mathtt{q}}=(\mathtt{q},\,\mathtt{r}\oplus b.\,(\mathtt{p}\oplus a_{1}.\mathtt{end}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}\mathtt{q}\,\&\,a_{2}.\mathtt{end}),\,\sigma_{0})\hskip 18.49988ptY^{\prime}_{\mathtt{q}}=(\mathtt{q},\,\mathtt{r}\oplus b.\,(\mathtt{p}\oplus a_{1}.\mathtt{end}\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\mathtt{q}\,\&\,a_{2}.\mathtt{end}),\,\sigma_{0}) In Y_{\mathtt{q}} , \mathtt{q} cannot instantiate the MC before it sends b to \mathtt{r} (i.e., Y_{\mathtt{q}} cannot reduce to Y^{\prime}_{\mathtt{q}} ). Namely, the system derived from \mathtt{G}_{P} cannot reach the state derived from \mathtt{G}_{P}^{\prime} where all configurations have instantiated c (yet \mathtt{q} has not sent b ). The preorder ‘ <: ’ is introduced to regulate this deferral of instantiations which may need to be interleaved with other actions. In the example above Y_{\mathtt{q}}<:Y^{\prime}_{\mathtt{q}} . The key rule for MC is given below (left). {\mathtt{L}} is the local type used to bootstrap the derivation at the configuration level (below right). Essentially, the other cases (except for axioms \mathtt{end}<:\mathtt{end} and \mathtt{t}<:\mathtt{t} ) are defined inductively, and the preorder is applied to systems pointwise. \begin{array}[]{c}\frac{\mathtt{L}_{1}^{\prime}\mathbin{<:}\mathtt{L}_{1}\hskip 16.38895pt\mathtt{L}_{2}^{\prime}\penalty\ \mathbin{<:}\penalty\ \mathtt{L}_{2}}{\mathtt{L}_{1}^{\prime}\,{\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c}\mkern 1.0mu}}\,\mathtt{L}_{2}^{\prime}\penalty\ \mathbin{<:}\penalty\ \mathtt{L}_{1}\mathrel{\mkern 1.0mu\blacktriangleright^{c}\mkern 1.0mu}\mathtt{L}_{2}}\qquad\qquad\frac{\mathtt{L}^{\prime}\mathbin{<:}{\mathtt{L}}}{(\mathtt{p},\mathtt{L}^{\prime},\sigma)\mathbin{<:}(\mathtt{p},{\mathtt{L}},\sigma)}\end{array} Lemma 4.1 (Bottom-up fidelity). Let \mathtt{G} be a global type reachable from an initial, aware, and balanced global type, and let Y_{\mathtt{G}}=\mathtt{G}\hskip-2.84526pt\upharpoonright\, . Then the following holds: (1) Y_{\mathtt{G}}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y\penalty\ \land\penalty\ \penalty\ \ell\neq\rho\penalty\ \penalty\ \penalty\ \penalty\ \Longrightarrow\penalty\ \penalty\ \penalty\ \penalty\ \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{{\ell}}}\penalty\ {\mathtt{G}^{\prime}}\quad\land\quad\exists Y^{\prime}.\penalty\ Y{\color[rgb]{0,0,1}\,\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\rho}}\penalty\ ^{\hskip-3.41432pt*\,}}{}Y^{\prime}\penalty\ \penalty\ \land\penalty\ \penalty\ Y^{\prime}<:\mathtt{G}^{\prime}\hskip-2.84526pt\upharpoonright\, (2) Y_{\mathtt{G}}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\rho}}\penalty\ Y\penalty\ \penalty\ \penalty\ \penalty\ \Longrightarrow\penalty\ \penalty\ \penalty\ \penalty\ Y_{\mathtt{G}}=Y=\mathtt{G}\hskip-2.84526pt\upharpoonright\, In case (1), if the action by \mathtt{G} is committing (say for \mathtt{p} ), then it may cause some of the messages in \mathtt{p} ’s queue in Y to become stale, hence a \rho action may be needed to restore correspondence. Case (2) highlights a property of projection: derived systems have no stale messages. Lemma 4.2 (Top-down fidelity). Let \mathtt{G} be a global type reachable from an initial, aware, and balanced global type, and let Y_{\mathtt{G}}=\mathtt{G}\hskip-2.84526pt\upharpoonright\, . Then the following holds: (1) \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}\,\pic@makebox@{\framebox}{framed=true}(3.0,6.0){}\,a}}\penalty\ {\mathtt{G}^{\prime}}\quad\Longrightarrow\quad\exists Y^{\prime}.\penalty\ \penalty\ \penalty\ Y_{\mathtt{G}}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}\,\pic@makebox@{\framebox}{framed=true}(3.0,6.0){}\,a}}\penalty\ \hskip-5.69054pt{\color[rgb]{0,0,1}\,\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\rho}}\penalty\ ^{\hskip-3.41432pt*\,}}Y^{\prime}\penalty\ \penalty\ \penalty\ \land\penalty\ \penalty\ \penalty\ Y^{\prime}<:\mathtt{G}^{\prime}\hskip-2.84526pt\upharpoonright\,\qquad(\,\pic@makebox@{\framebox}{framed=true}(3.0,6.0){}\,\in\{!,?\}) (2) \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\nu c}}\penalty\ {\mathtt{G}^{\prime}}\quad\Longrightarrow\quad\exists Y^{\prime}.\penalty\ \penalty\ \penalty\ Y_{\mathtt{G}}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\overrightarrow{\nu c}}}\penalty\ Y^{\prime}\penalty\ \penalty\ \penalty\ \land\penalty\ \penalty\ \penalty\ Y^{\prime}<:\mathtt{G}^{\prime}\hskip-2.84526pt\upharpoonright\, Case (1) is symmetric to case (1) of bottom-up fidelity. In case (2) action \nu can be immediately matched with several actions \nu by Y (others may be deferred by ‘ <: ’). The operational correspondence is formulated in terms of a weak relation over pairs of global types and systems, where \nu and \rho are renamed as \tau . We write {\color[rgb]{0,0,1}\,\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }}\penalty\ ^{\hskip-3.41432pt*\,}} for a possibly empty sequence of \tau actions and define {\color[rgb]{0,0,1}\,\mathrel{{\mathrel{\to}^{\ell}}}\,}={\color[rgb]{0,0,1}\,\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }}\penalty\ ^{\hskip-3.41432pt*\,}}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ {\color[rgb]{0,0,1}\,\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }}\penalty\ ^{\hskip-3.41432pt*\,}} if \ell\neq\tau and {\color[rgb]{0,0,1}\,\mathrel{{\mathrel{\to}^{\ell}}}\,}={\color[rgb]{0,0,1}\,\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\penalty\ }}\penalty\ ^{\hskip-3.41432pt*\,}} otherwise. Definition 4.3 (Weak Correspondence). A relation \mathcal{R} over (\mathtt{G},Y) is a weak correspondence if whenever (\mathtt{G},Y)\in\mathcal{R} then: (1) If \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \mathtt{G}^{\prime} then Y{\color[rgb]{0,0,1}\,\mathrel{{\mathrel{\to}^{\ell}}}\,}Y^{\prime} and (\mathtt{G}^{\prime},Y^{\prime})\in\mathcal{R} ; (2) If Y\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ Y^{\prime} then \mathtt{G}\,{\color[rgb]{0,0,1}\,\mathrel{{\mathrel{\to}^{{\ell}}}}\,}\,\mathtt{G}^{\prime} and Y^{\prime}{\color[rgb]{0,0,1}\,\mathrel{{\mathrel{\to}}}\,}Y^{\prime\prime} with (\mathtt{G}^{\prime},Y^{\prime\prime})\in\mathcal{R} . Two states \mathtt{G} and Y are weakly correspondent, written \mathtt{G}\approx Y , if and only if there exists a weak correspondence \mathcal{R} such that (\mathtt{G},Y)\in\mathcal{R} . Theorem 4.4. Let \mathtt{G} be reachable from an initial, aware and balanced global type, then \mathtt{G}\approx\mathtt{G}\hskip-2.84526pt\upharpoonright\, . ( Theorem 4.4 ) follows from top-down and bottom-up fidelity, since Y<:\mathtt{G}\hskip-2.84526pt\upharpoonright\, implies \mathtt{G}\approx Y , which is mechanical by induction. 4.4. Further Properties of Systems Local progress ensures that each configuration in a system can make further actions, unless it is in a final state (or it is final for short). Configuration (\mathtt{p},L,\sigma) is final if L\equiv\mathtt{end} , where \equiv is the structural equivalence defined by the following rules: \mathtt{end}\blacktriangleright\bullet\equiv\bullet\blacktriangleright\mathtt{end}\equiv\mathtt{end}\blacktriangleright\mathtt{end}\equiv\mathtt{end} . Observe that L\equiv\mathtt{end} implies that \mathtt{p} has no further actions in L and is committed in all MC in L . Definition 4.5 (Local Progress). Y enjoys progress if for all Y^{\prime} reachable from Y : (\mathtt{p},\mathtt{L},\sigma)\penalty\ \text{ in }\penalty\ Y^{\prime}\penalty\ \text{ is not final }\quad\Rightarrow\quad Y^{\prime}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{}\hskip-3.44444pt^{*}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \penalty\ \penalty\ \land\penalty\ \penalty\ \mathtt{sbj}(\ell)=\mathtt{p} The Corollary 4.6 of Theorem 4.4 lifts global progress ( Theorem 3.13 ) to systems. Corollary 4.6 (Local Progress). If \mathtt{G} is initial, aware and balanced then \mathtt{G}\hskip-2.84526pt\upharpoonright\, enjoys progress. From local progress we further establish orphan message freedom (OMF), which states that every message in a queue can eventually be received (see Appendix G for details). Theorem 4.7 (name=OMF). Let Y,(\mathtt{q},\mathtt{L},\sigma) be a system reachable from the projection of an initial, aware, and balanced global type. If \sigma[\mathtt{p}]=\vec{m_{1}}\cdot(a_{k},\pi)\cdot\vec{m_{2}} with (a_{k},\pi)\not\in\vec{m_{1}} , then there exists Y^{\prime},(\mathtt{q},\mathtt{L}^{\prime},\sigma^{\prime}) reachable from Y,(\mathtt{q},\mathtt{L},\sigma) such that either (1) \mathtt{stale}(\pi,\mathtt{L}^{\prime}) , or (2) Y^{\prime},(\mathtt{q},\mathtt{L}^{\prime},\sigma^{\prime})\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?(a_{k},\pi)}}\penalty\ . OMF in MST was first formulated ( 26 ; 27 ) to state that final (terminated) states have empty queues. Our Theorem 4.7 is more general because it also covers non-terminating systems. In our setting, we can state the weaker property of Deniélou and Yoshida modulo stale message purging as: if Y is final and derived from the projection of an initial, aware and balanced \mathtt{G} , then for all (\mathtt{p},\mathtt{L},\sigma) in Y , \mathsf{gc}(\mathtt{L},\sigma)=\emptyset . This follows immediately from Theorem 4.7 : if a non-stale message were present in Y , by Theorem 4.7 there would exist Y^{\prime} reachable from Y where that message is consumed or stale, contradicting the finality of Y . A stronger version of OMF ( 17 ) has been studied in the setting of (binary) session types with fairness conditions by 48 . Due to MC, our Theorem 4.7 first differs by considering garbage collection (case (1) in Theorem 4.7 ). Secondly, their fair termination condition enforces that every message is necessarily received in every possible execution, whereas our Theorem 4.7 ensures that every enqueued message may always be possibly received or garbage collected (e.g., given \mu\mathtt{t}.\,\mathtt{p}\rightarrowtriangle\mathtt{q}:a.\,\mathtt{t} , it is always possible for \mathtt{q} to receive but the unfair execution where \mathtt{p} sends forever while \mathtt{q} never receives is also possible). We leave to future work an investigation of fairness conditions à la 19 ; 48 for asynchronous MC in MST. Section 6 gives further comparisons with 19 . 5. Implementation and Further Examples 5.1. Toolchain Implementation Global protocol validation We have implemented mMST as an extension to the Scribble protocol language ( 60 ; 35 ) . The practical syntax for our MC is as demonstrated in Section 2 . Following our formal theory, our implementation allows MC to be combined with the standard MST constructs for regular directed choice (non-mixed branch/select) and recursion to express a range of patterns and DS constructs found in practical applications. Our toolchain internally translates Scribble specifications to a representation based on our formal definitions and syntactically checks the source protocol for (a) the well-formedness of committing message labels ( Definition 3.4 ), (b) awareness ( Definition 3.9 ) and balance ( Definition 3.12 ), and (c) projectability ( Section 4.2 ) onto all roles. In our current implementation, checking (b) syntactically means inferring role occurrences and dependencies between roles as written in the source protocol without (semantically) unfolding recursive types. This is sound: such syntactically inferred dependencies conservatively imply our formal conditions. Code generation. The toolchain implements projection of global types to local types following the formal theory. Each local type is then translated to an event-driven finite state machine (EFSM) representation. As described in Section 2.2 , from the EFSM we generate two Erlang modules for each role: a role module (RM) and a callback module (CM). In Figure 3 , we showed the CM for role B . In Figure 7 , we show the corresponding RM for B . The RM builds on gen_statem , providing an EFSM structure to manage state transitions and message passing in accordance with the protocol. Specifically, it provides state function definitions ( Figure 7 , lines 27-40), and callback specifications ( Figure 7 , lines 2-8) that must be implemented by the CM to handle incoming messages and internal events. It also provides functions for sending messages ( Figure 7 , lines 17-23). Moreover, it leverages gen_statem ’s asynchronous selective receive to defer out-of-order events by returning a postpone action (e.g. keep_state, Data, [postpone]) (lines 27-28), requeuing them until the state machine transitions into a state that can properly handle them. Following Erlang convention, the RM excludes any application-specific logic, which instead is left to callbacks in the CM. ⬇ 1 % -------- Callback specifications -------- 2 - callback s5 ( term (), { atom ()}, state_data ()) -> { stop , normal , state_data ()}. 3 - callback s1 ( term (), { atom ()} | { pid (), { term ()}}, state_data ()) -> 4 { next_state , s5 , state_data (), [{ next_event , internal , { ’TOc’ }}]} | { keep_state , state_data ()} | 5 { keep_state , state_data (), [ postpone ]} | { next_state , s2 , state_data (), [{ next_event , internal , { a3 }}]}. 6 - callback s2 ( term (), { atom ()}, state_data ()) -> 7 { next_state , s3 , state_data (), [{ next_event , internal , { a4 }}]} | { keep_state , state_data ()}. 8 - callback s3 ( term (), { atom ()}, state_data ()) -> { stop , normal , state_data ()}. 9 %% -------- Record and type definitions for maintaining state -------- 10 - record ( data , { a_pid :: pid (), c_pid :: pid () }). %% Process identifiers for roles A and C. 11 %% -------- Send helpers -------- 12 send_s1_TOa ( APid , Data ) -> gen_statem : cast ( APid , { self (), { ’TOa’ }, Path }). 13 send_s5_TOc ( CPid , Data ) -> gen_statem : cast ( CPid , { self (), { ’TOc’ }, Path }). 14 send_s3_a4 ( APid , Data ) -> gen_statem : cast ( APid , { self (), { a4 }, Path }). 15 send_s2_a3 ( CPid , Data ) -> gen_statem : cast ( CPid , { self (), { a3 }, Path }). 16 %% ---------- Callback function definitions delegate the processing to the CM ---------- 17 s1 ( EventType , { APid , { a1 }, Pi }, Data ) -> 18 case stale ( Pi , left ) of 19 true -> { keep_state , Data }; 20 false -> Side = CallbackModule : s1 ( EventType , { APid , { a1 }}, Data ) 21 case Side of { next_state , s6 , _ } -> commit_entry (? MC1 , left ), Side ; 22 { next_state , s3 , _ } -> commit_entry (? MC1 , right ), Side 23 end ; 24 end ; 25 s1 ( EventType , { ’TOa’ }, Data ) -> Side = CallbackModule : s1 ( EventType , { ’TOa’ }, Data ) 26 case Side of { next_state , s6 , _ } -> commit_entry (? MC1 , left ), Side ; 27 { next_state , s3 , _ } -> commit_entry (? MC1 , right ), Side 28 end . 29 s5 ( EventType , ’TOc’ , Data ) -> CallbackModule : s5 ( EventType , ’TOc’ , Data ). 30 s2 ( EventType , a3 , Data ) -> CallbackModule : s2 ( EventType , a3 , Data ). 31 s3 ( EventType , a4 , Data ) -> CallbackModule : s3 ( EventType , a4 , Data ). Figure 7. Extract from the RM generated for B in Timeout , implementing its protocol- and role-specific gen_statem behaviour and declaring the callback functions to be implented by the CM. In mixed choices, participants may receive messages from non-selected branches until all participants become committed. To prevent protocol violations stemming from these stale messages, the toolchain implements event queue management and state data tracking within the gen_statem framework. The implementation follows the theory, and derives the stale messages to be purged from the global type, as defined in Section 4.1 . gen_statem maintains an event queue where incoming events are enqueued and dispatched sequentially based on arrival order and their priority, with internal events being prioritised over external events. Each incoming MC message carries a path Pi recording the sides taken through active MCs. The RM keeps a local commitment map, and as illustrated in Figure 7 , lines 22-26, when an event is received the RM module purges the event if the path Pi is stale, otherwise it forwards the event to the CM module. Runtime requirements. Our implementation uses Erlang’s core features for process spawning and asynchronous message passing, and the built-in gen_statem library for executing event-driven finite state machines (EFSMs). However, a runtime for our theory can be implemented in any setting that supports event-driven concurrency and asynchronous messaging, over which a framework for session-based EFMSs can be readily developed ( 58 ) if not directly supported as in Erlang. Our protocol validation and projection is independent of Erlang. 5.2. Expressiveness by Examples Table 1 summarises a range of examples from MST literature that we have extended with mixed choice (MC) to support features such as timeouts and exceptions. Our MC allows use cases like SMTP to be expressed more fully than in prior MST systems due to supporting timeouts (prior works simply disregarded that aspect). Our examples test the static elements of protocol validation, projection, EFSM translation and Erlang module generation. We also implemented minimal but functional skeleton programs for each role of the examples to test the runtime I/O and event handling dynamics, and embedded MC mechanisms such as stale message purging. However, our minimal implementations generally do not perform the full application logic of the examples. Table 1. MST examples extended with asynchronous mixed choice (MC). M=Multiparty B/S=Branch/Select Rec=Recursion nMC=nested MC ndMC=non-directed MC GC=purging Example M B/S Rec MC nMC ndMC GC Source Calculator \checkmark \checkmark \checkmark \checkmark [Hu and Yoshida, 2016] CircuitBreaker \checkmark \checkmark \checkmark \checkmark \checkmark \checkmark [Lagaillardie, Neykova and Yoshida 2022] DistributedLogging \checkmark \checkmark \checkmark \checkmark [Lagaillardie, Neykova and Yoshida 2022] Fibonacci \checkmark \checkmark \checkmark \checkmark [Hu and Yoshida, 2016] SMTP \checkmark \checkmark \checkmark \checkmark \checkmark [Hu and Yoshida, 2016] TwoBuyer \checkmark \checkmark \checkmark \checkmark \checkmark \checkmark [Honda, Yoshida, Carbone, 2008] TravelAgency \checkmark \checkmark \checkmark \checkmark \checkmark [Hu, Yoshida and Honda 2008] OnlineWallet \checkmark \checkmark \checkmark \checkmark \checkmark \checkmark [Neykova, Yoshida and Hu, 2013] Distributed system constructs. A key motivation for mMST is to provide a core construct that can express a range of important constructs – building blocks of many practical distributed systems – that were previously only supported by bespoke and disparate MST extensions. These include exceptions ( 11 ) , interrupts ( 23 ) , timeouts ( 49 ; 32 ) , and failure handling ( 57 ) . A basic timeout pattern was illustrated in Section 2 ; exceptions are similar. We illustrate interrupts and failure handling below. Failure handling . We give an example of MC drawn from the major topic of failure handling and fault-tolerance in MST ( 57 ; 58 ; 2 ; 50 ; 8 ) . The existing work typically models application protocols assuming that failure detection (FD) is implicitly provided by the runtime infrastructure. With MC as a core construct, we can now explicitly model such mechanisms and how role behaviours may depend on them. Figure 8 (left) gives a small example, where Worker W is a failure-prone role and the observer FD represents the FD service, based on the use cases of 57 ; 58 featuring heartbeat-based FD. We specify it as a recursive MC where in each iteration (i.e., unfolding of the recursive type) FD waits to receive a heartbeat ( HB ) from W with the option to send a Crash notification to M (e.g., upon a timeout, connection error, or other failure condition). The annotation on L 11 is given by a simple variant of our core theory where protocol validation prohibits further usage of a role considered failed (i.e., W cannot occur again in the continuation of the protocol after L 11 ). The Timeout message is useful if the connection is actually still live, allowing W to handle its own (reported) demise, but can be considered redundant otherwise. Following our theory, protocol validation allows the awareness of W in the LHS to be transitively relayed from FD to M via OK , then to W via more . ⬇ 1 global protocol FailH ( role M , role W , role FD ) { 2 init ( Data ) from M to W ; 3 rec X { 4 mixed { // LHS 5 HB () from W to FD ; 6 OK () from FD to M ; 7 result ( Data ) from W to M ; 8 more ( Data ) from M to W ; 9 continue X ; 10 } or { // RHS 11 Timeout () from FD to W ; @ ’failed W’ 12 Crash () from FD to M ; 13 } } } ⬇ 1 @ ’explicit-observer-left-commits’ 2 global protocol Interr ( role P , role Q ) { 3 mixed { // LHS 4 Start () from Q to P ; 5 rec X { 6 choice at Q { 7 More () from Q to P ; continue X ; 8 } or { 9 Stop () from Q to P *; // P commits 10 Ack () from P to Q ; 11 } } 12 } or { // RHS 13 Interrupt () from P to Q ; } } Figure 8. Heartbeat-based failure detection (left), and an asynchronous interrupt (right). Interrupts. Recall the interrupt patterns using MC in Example 3.11 . The interrupt pattern can be expressed in our Scribble extension as in Figure 8 (right). We make an option for the user to explicitly indicate the committing interactions for observers in the LHS of an MC (as opposed to the observer implicitly committing on the first such message received as in the core theory). The explicit committing interaction is marked by a * on the observer role occurrence, e.g., P* on Line 9 . 5.3. Case Study: RabbitMQ We apply our toolchain to a non-trivial, real-world case study, RabbitMQ. The toolchain can generate code for each participant in the chosen subset of the AMQP protocol, while also allowing for interoperability: the code generated for one participant (e.g., Consumer) can interoperate with pre-existing RabbitMQ implementations. The Advanced Message Queuing Protocol 5 5 5 https://www.amqp.org/ (AMQP) is an open-standard protocol designed for message-oriented middleware. RabbitMQ, a widely-used open-source message broker adhering to the AMQP standard, leverages the Erlang client library amqp_client 6 6 6 https://github.com/rabbitmq/rabbitmq-server/tree/main/deps/amqp_client to facilitate interaction between Erlang and Elixir applications and RabbitMQ nodes. Within this ecosystem, the amqp_selective_consumer module, implemented alongside its behaviour amqp_gen_consumer , plays a crucial role in managing message consumption with precise control over delivery and cancellation. Notably, amqp_selective_consumer is already implemented as a state machine using Erlang’s gen_server behaviour; however, this implementation is relatively ad-hoc. We replace the amqp_selective_consumer , and its implemented behaviour amqp_gen_consumer from the RabbitMQ Erlang client library, amqp_client with a behaviour and a callback module generated from a session type representation of the protocol. We model the relevant part of the AMQP protocol in Scribble, Figure 9 , capturing the interactions between the consumer C , channel H , and server S roles for selective message delivery. The consumer registers with the channel and initiates a basic_consume request, which is forwarded to the server. The server responds with basic_consume_ok , confirming the consumer’s subscription. The SelectiveMessageDelivery recursive block models ongoing message exchanges, using an MC construct to represent message processing on one hand and cancellation on the other. MC is essential for accurately modelling the concurrency and asynchronous behaviour in AMQP. It allows the protocol to express that either the server may deliver a new message – basic_deliver , or the consumer may choose to cancel the subscription – basic_cancel . Our toolchain validates this global type, projects it to a local type for each role, and constructs an EFSM representation of each local type. For the consumer role, C , the toolchain generates a correct-by-construction behaviour and callback modules. The generated modules replace amqp_selective_consumer and amqp_gen_consumer , implementing the same interfaces expected by other components. All features of amqp_selective_consumer are preserved, including message consumption, and cancellation. We use RabbitMQ’s existing test suite to validate the new amqp_selective_consumer implementation. ⬇ // roles: C = Consumer, H = Channel, S = Server global protocol AMQP ( role C , role H , role S ) { register_default_consumer () from C to H ; basic_consume ( consumer_tag , nowait ) from C to H ; basic_consume ( consumer_tag , nowait ) from H to S ; basic_consume_ok ( consumer_tag ) from S to H ; basic_consume_ok ( consumer_tag ) from H to C ; rec SelectiveMessageDelivery { mixed { basic_deliver ( consumer_tag , delivery_tag , exchange , routing_key ) from S to H ; // Continued on right column... ⬇ process_message () from H to C ; basic_deliver ( consumer_tag , delivery_tag , exchange , routing_key ) from H to C ; processing_complete ( delivery_tag ) from C to H ; update_delivery_state ( delivery_tag ) from H to S ; continue SelectiveMessageDelivery ; } or { basic_cancel ( consumer_tag , nowait ) from C to H ; basic_cancel ( consumer_tag , nowait ) from H to S ; basic_cancel_ok ( consumer_tag ) from S to H ; basic_cancel_ok ( consumer_tag ) from H to C ; } } } Figure 9. Subset of AMQP using a recursive MC in our extended Scribble. 6. Related Work, Limitations and Future Work This paper presents the first asynchronous multiparty session type system with a core construct for mixed choice. There are two main lines of related work in the literature: session types with synchronous mixed choices, and MST extensions for bespoke exception-like constructs. The literature includes several works on synchronous mixed choices for binary ( 55 ; 12 ; 13 ) and multiparty ( 14 ; 40 ; 39 ; 51 ) session types. In synchronous settings, mixed choices behave very similarly to regular ( non -mixed) choice: both can be modelled by an atomic reduction step (e.g., G_{1}\mathop{+}G_{2}\mathbin{\rightarrow}G_{i}^{\prime} for i\mathop{\in}\{1,2\} and G_{i}\mathbin{\rightarrow}G_{i}^{\prime} ). Reasoning about safety of asynchronous mixed choices (MC) and disciplining the inherent race conditions is a substantially different endeavour, as shown by our developments through the design of our MC, static validation, runtime mechanisms and metatheory. We note the work of 49 on asynchronous binary session types with mixed choice, where each choice has a timing constraint. Their system allows choices with a mix of input and output actions, but they statically enforce that actions in different directions are never viable at the same point in time . Similar approaches based on timed session types ( 32 ) share this limitation. By contrast, we deal with bona fide asynchronous MC where both communication directions w.r.t. all pairs of participants are concurrently viable. This paper aims to distill the essence of mixed choice in asynchronous (M)ST, various aspects of which were studied in several areas; e.g., interaction exceptions ( 11 ) (binary), interaction handlers ( 10 ) (with synchronous triggers), interruptible blocks ( 23 ) (where default/interrupted blocks share common continuations), and internal exceptions ( 28 ) (local failure control, no type construct). We have shown how MC can express multiparty asynchronous timeouts and interrupts; exceptions are similar. A crucial area for real-world applicability of session types is support for failure handling, where aspects of mixed choice arise intrinsically. 57 ; 58 developed an MST system with try-handle constructs for handling partial failures of a protocol due to (suspected) participant crashes. In these works a process may be faced with a choice between outputs in the normal protocol flow mixed with potential inputs related to failure detection/notification. The (supposed) failure of a participant rules out all interactions with that participant thereafter. By contrast, our MC has a finer-grained notion of commitment that is per instance of an MC (not per protocol). Section 5.2 demonstrated such a failure handling pattern using our MC. 2 present an approach to failure handling in MST that avoids syntactic extensions (cf. ( 4 ) ). Their system designates a special message label \mathsf{crash} to denote failure of the “sending” participant, which otherwise behaves as a regular label in choice constructs. E.g., \mathtt{p}\mathbin{\rightarrowtriangle}\mathtt{q}:\{a.\,{\color[rgb]{0.5,0.5,0.5}\mathtt{G}_{1}},\mathsf{crash}.{\color[rgb]{0.5,0.5,0.5}\mathtt{G}_{2}}\} specifies that \mathtt{q} awaits either message a from \mathtt{p} or notification of \mathtt{p} ’s crash. As in the related work above, crash events may occur concurrently with the I/O actions of the main protocol flow and their system incorporates some related machinery (e.g., queue cleaning); however, neither their user-level types nor processes have explicit constructs for mixed choice. See Appendix A for further notes on the above works. Communicating systems featuring mixed choice have been studied outside of session types. Communicating automata ( 6 ) for instance do not rule out mixed choices but progress is, in general, undecidable. 42 present a tool that infers behavioural types ( 37 ) for channel-based, shared-memory concurrency programs in Go. Their system permits mixed choice for the select construct and assumes finitely buffered channels, enabling decidable model checking (e.g., deadlock-freedom) of the inferred types. Our work instead supports asynchronous communication over unbounded channels. Recently, 44 presented the first sound and complete projection method for global types generalised with sender-driven choice ( \mathtt{p}\mathbin{\rightarrow}\{\mathtt{q}_{i}:m_{i}.G_{i}\}_{I} ). Their automata-theoretic approach separates local machine synthesis from implementability checking, but, like 45 , do not support mixed choice. By contrast, our work builds on classical MST with regular (non-mixed) choices restricted to directed choice and syntactic projection. This is because our asynchronous MC is influenced by the other works discussed above on, e.g., interrupts and failure handling. 19 presented an MST system for fair termination in a synchronous session \pi -calculus without mixed choice. Their system guarantees processes (with multiple sessions) will fairly terminate by combining: a validation that session types always potentially terminate, a restricted fusing of session initiation and process spawning ( 59 ; 9 ) , a notion of ranking that limits processes to finite behaviours, a liveness-preserving subtyping relation, and a fairness assumption on executions (potential termination leads to actual termination). There may be connections between our notion of clear termination, that is per MC, with their notion of (whole) protocol termination; at present, our system differs in that we allow a session to be unbounded provided each MC individually satisfies awareness. 48 recently developed fair termination for asynchronous binary sessions (as mentioned in Sec. 4.4 ). Limitations and future work. Our system builds on classical MST with regular choices restricted to directed choice, and syntactic projection and merge ( 54 ; 52 ) . This yields a projection that is sound but not complete in the base MST constructs (directed choice, recursion), let alone with MC. In future work, we plan to investigate (conservative forms of) mixed choice in the generalised automata-theoretic setting of 44 . The challenges include reconciling their language-based approach with our mechanisms (e.g., stale message purging) and metatheory (e.g., operational correspondence and preservation of projection). Another issue is that their projection yields state machines that are more general than local types: accepting (terminating) states may have outgoing transitions, and choice branches may be unbalanced across roles. Such generality must be reconciled with the objective of our system (and classical MST) that all projected behaviours, including MCs, be realisable as fully distributed processes; e.g., we typically aim to rule out protocols where termination could be non-deterministic (cf. Def. 3.9 ). Building on the above, 53 recently extended projection to a larger class of automata-based global specifications, but show that the projectability of mixed choice in their more general setting is undecidable. Their negative result motivates pragmatic approaches to supporting mixed choice such as in this paper. The automata-based system of 43 may also provide avenues for lifting directed choice and generalising our protocol validation. One of our present limitations is that our system does not incorporate delegation ( 30 ; 4 ) . Considering our MC concepts (e.g., stale message purging and path identifiers) in a setting with delegation is a topic for future work. An interesting question is how fair multiparty termination ( 19 ) may be extended to asynchronous mixed choices. One direction could be to investigate fair termination for our notion of MC global/local types and formalise a process-level language. Unlike the ‘multithreaded’ \pi -calculi in the mentioned works, however, the model of concurrency in our practical Erlang setting is event-driven ( 33 ; 58 ) and does not have a specific primitive for fusing session initiation and process spawning. Adapting their notion of static typing of process ranks may be a challenge in languages such as Erlang. Data-Availability Statement The source code of our toolchain, examples and RabbitMQ case study is available online. 7 7 7 https://github.com/rhu1/scribble-gt-scala/tree/artifact It will be submitted for review as an artifact. Acknowledgements. This work was partially funded by EPSRC project EP/T014512/1, EP/T014628/1 (STARDUST). Appendix A Additional notes on related work (cf. Section 6 ). Appendix B Additional notes on handling multiple sessions Appendix C Full definitions of committing and non-committing label sets (cf. Section 3.1 ). Section D.8 Progress of global types: Omitted definitions and proofs (cf. Section 3.3 ). Appendix E Local types: Full definitions (cf. Sections 4.1 and 4.2 ). Appendix F Operational correspondence: Omitted definitions and proofs (cf. Section 4.3 ). Appendix G Orphan messages: Omitted definitions and proofs (cf. Section 4.4 ). Appendix A Additional Notes on Related Work Mixed choice in binary sessions. 55 developed a binary session type system for synchronous sessions with mixed choice. 12 ; 13 further established a type preservation property for mixed sessions, an embedding of classical sessions ( 56 ) into the mixed sessions, and a partial encoding in the reverse direction. All of these works are limited to binary sessions with synchronous communication, where mixed choice subsumes non-mixed choice. By contrast, mixed choice in (safe) asynchronous sessions gives rise to (transient) inconsistencies between the views of the protocol from different participants, which are precluded by the power of synchrony. 49 developed a system with binary session types for mixed choice with timing constraints for asynchronous sessions. Their system syntactically allows two-party choices with a mix of input and output actions with the (statically enforced) restriction that actions of different directions are never viable at the same point in time . By contrast the entire purpose of our system is to permit and safely deal with truly asynchronous mixed choices where both communication directions w.r.t. all pairs of participants are concurrently viable. In the binary settings of the above works, note that the notion of fidelity is in a sense moot since two-party local types effectively coincide with their (conceptually) associated global type. By constrast, multiparty local type projections are, in general, partial w.r.t. the global type, necessitating our developments to establish an operational correspondence between asynchronous global and local types featuring mixed choice (cf. Section 4 ). Mixed choice in synchronous multiparty sessions. In MST, existing work on mixed choice has been limited to synchronous sessions. A consequence is that the constructs for mixed choice in all the following works are symmetric in nature, unlike the asymmetric construct we have developed in this paper for safety in asynchronous sessions. 14 developed a set-theoretic semantic framework for global types and multiparty sessions based on a trace semantics. Although their global types include the syntax for G\vee G^{\prime} , the choice constructs in their local types are further syntactically constrainted to T\oplus T^{\prime} or T+T representing the traditional internal- only and external- only choices. Moreover, their trace semantics does not model the intermediary (and potentially inconsistent) states that may arise from asynchronous mixed choice, and each trace element denotes an atomic interaction between the sender and receiver, in contrast to the intermediary states represented by, e.g., \mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}} types (e.g., Section 3 ) that expose the inherent race conditions. 40 studied weak bisimulation between global and local types featuring the ‘ + ’ operator for choice in a synchronous system. They informally remark on encoding a form of asynchrony by representing buffered channels explicitly as roles, e.g., encoding an asynchronous p\rightarrowtriangle_{a}q interaction as the pair of synchronous interactions p\rightarrowtriangle_{s}b_{pq}.b_{pq}\rightarrow_{s}q where b_{pq} is a role that represents a message buffer from p to q . However, this does not amount to asynchrony as we model in this paper because a mixed choice becomes (p\rightarrowtriangle_{s}b_{pq}.{\color[rgb]{0.5,0.5,0.5}G_{1}^{\prime}})+(q\rightarrowtriangle_{s}b_{qp}.{\color[rgb]{0.5,0.5,0.5}G_{2}^{\prime}}) where by their (synchronous) semantics either output action by p or q instantly commits all roles to that branch and precludes the other action from occurring, thus precluding any intermediary states and the problematic race conditions. 39 present rules for extending a similar simulation approach to processes featuring the same formulation of ‘ + ’ for (mixed) choice as 40 . Their system is again synchronous with the same operational semantics; all the preceding comparison points with 40 apply here. 51 present a typing system between local types and processes with mixed choice. Their system is synchronous and their work does not include global types nor operational correspondence between global and local types as in our system. We note, however, that our present paper shares some simplifications with the above works. For example, our system focuses on modelling the semantics of a single session; this is the same as in all of the MST works mentioned above, Consequently, none of these works nor our present paper has studied mixed choice for multiparty sessions in the presence of session delegation ( 30 ) , where a session message carries another session channel as a payload. Exception-like communications patterns in session types. As discussed in Section 1 , mixed choice is at the heart of many crucial communication patterns in real-world distributed systems. One motivation for our paper is to distil the essence of mixed choice in asynchronous MST, various aspects of which have been studied in several prominent areas. Exceptions and interrupts. 11 developed a binary session type system for processes with interaction exception handlers. Their try-catch type \alpha\{\![\beta]\!\} specifies a normal protocol \alpha , and an exceptional protocol \beta triggered by throwing an exception. This allows situations where a process may be faced with, say, an input in its normal protocol but an output in the triggered exception handler, and dually for its binary peer. Their approach introduces a notion of meta reduction P\mathop{\Searrow}P^{\prime} to deal with propagating exceptions, nested exceptions and queue cleaning, which is related to our garbage collection. 10 extend MST with interaction handlers that require reasoning about concurrency of exceptions raised by multiple peers. Their approach introduces an exception environment \Sigma into the reduction relation \Sigma\vdash P\rightarrow\Sigma^{\prime}\vdash P^{\prime} , where \Sigma records the raised exceptions. It is notable, however, that \Sigma is operated on synchronously and atomically by all multiparty participants, i.e., raising an exception notifies all parties instantly. 23 proposed types for interruptible blocks in multiparty sessions. In their type \{\!|G|\!\}\langle\ell\text{ by }r\rangle;G^{\prime} , the G can be interrupted by r at any point. Whether or not G is interrupted it is followed by G^{\prime} , unlike our present paper that supports safe mixed choice between different continuations. Their restriction permits a synchronous operational semantics for global types (the derivative relation) with atomic steps for both interactions and the signalling of interrupts. 28 develop a functional language with binary session types and primitives for raising and handling exceptions. Their system focuses on exceptions as a local control flow feature external to their session types, i.e., there is no type construct for exceptions, unlike our mixed choice in this paper or all the other works discussed above. 7 ; 8 recently developed timeout branches for a low-level MST where messages can be arbitrarily reordered and lost, which is a radically different communication model than in our paper and the other works mentioned above. Consequently, their notion of safety is weaker than in standard MST: they enforce that timeout branches are always defined, and ensure that if a message is received then it has the expected payload. Failure handling. A crucial area towards the application of session types to real-world distributed systems is support for failure handling, where aspects of mixed choice arise naturally. 57 develop an asynchronous MST system with a try-handle construct for handling partial failures of a protocol due to participant crashes. They target distributed system with central coordinators for reliable failure detection. By contrast, 58 developed an asynchronous MST system that extends subsessions ( 24 ) with handlers for peer -based unreliable failure detection. These works both treat patterns where a process may be faced with a choice between outputs in the normal protocol flow mixed with potential inputs related to failure detection/notification. Participant failure handling is an instance of mixed choice where the (supposed) failure of a participant rules out all interactions with that participant henceforth, unlike our mixed choice in this paper where the fine-grained notion of commitment is per instance of a mixed choice (a participant failure could be considered a coarse-grained commitment to all active and future instances of a particular mixed choice). Practical MST frameworks based on API generation from global protocols. Our paper shares the motivation of a range of works on developing MST frameworks for practical applications, e.g., ( 34 ; 15 ; 61 ) . Like the mentioned works, our overall framework has a two-stage design: (i) formal metatheory of global and local types (eschewing a process-level language) for validating protocol specifications, and (ii) a practical methodology for implementing MST-based sessions. Also like the mentioned works and others based on Scribble ( 35 ) , our practical methodology provides a toolchain for formally-grounded protocol validation and projection (based on the theory), and correct-by-construction code generation and/or runtime mechanisms for processes. Some works offload aspects of the protocol validation to supplementary methods outside the core syntactic type system, including model checkers ( 52 ) and SMT solvers ( 46 ; 15 ; 61 ) . Regarding the code generation and/or runtime mechanisms aspect, 34 developed a tool for generating protocol-specific runtime monitors for sessions in Python; 15 employed API generation for Go backed up by Z3 for solving indexing constraints in role-parametric types; and 61 developed types generation for static refinement typing in F ⋆ . In this paper, we develop code generation for protocol- and role-specific gen_statem callbacks and runtime mechanisms for automated stale message purging. As discussed, a key motivation for this paper is to develop a core construct for MC to capture and unify the essence of practical constructs such as exceptions, timeouts and failure handling. Ultimately, a goal for the research community is to develop a complete system that can integrate the full breadth of features needed by many practical applications in addition to MC patterns, such as parameterisation of protocols ( 25 ; 15 ) and dynamic topologies ( 36 ; 16 ) . Other MST works that focus on a formal theory of global-local types without a process-level language include works on richer global types and completeness of projection ( 45 ; 44 ) , and the semantics of multiparty sessions ( 14 ) . Appendix B Handling Multiple Sessions The key properties in our metatheory are the progress of valid global types, and the operational correspondence (fidelity) between a valid global type and its distributed local type projections; the latter entails a preservation property for projection, and transfers global progress to the local level. These results pertain formally to a single multiparty session. As such, our toolchain is primarily designed at present to generate a set of Erlang modules from one source protocol and ensure the aforementioned (single-session) properties. Nevertheless, a programmer may (e.g.) use the modules of multiple, separate protocols to implement a multi-session program. We can informally outline the pragmatic conditions for (multi-session) progress in our practical framework. There are two main facets. Local computations and inter-session dependencies. The first facet concerns the preconditions (i.e., assumptions) of our practical framework regarding local computations and events. Section 2 described the usage contract of our toolchain regarding the generated Erlang modules: the user must not modify the generated protocol- and role-specific module called the Role Module (RM), and can only modify the generated template callback module called the Callback Module (CM) according to the pre-generated structures of the EFSM and callback functions. Two key subconditions related to the latter are that the user must ensure: • Any internal or local computation event required to fire a pending callback will eventually occur. • Beyond its specific session I/O actions, every fired callback performs only non-blocking actions (e.g., local computations), and eventually terminates successfully to cede control back to the Erlang runtime (in order to fire the next callback). Note, these conditions are independent of whether a program has a single session or multiple sessions. In short, it is the user’s responsibility to ensure the correctness of local computations, i.e., all Erlang code beyond session I/O and callback actions, including arithmetic/logical expressions, general data processing and library calls. To implement a multi-session program, the user generates the (separate) RM and CM modules for the relevant roles of each protocol, and implements the necessary callbacks of each CM. Inter-session dependencies that are internal to a local program can be expressed in various ways according to the dependency. To illustrate, take the two protocols in Figure 10 . Consider implementing one Alice program to participate in two sessions, one for each protocol. Figure 11 gives two rudimentary examples of cross-session dependencies (we mention alternative and safer approaches below under “Future work”). • (Left) The start of one session is chained to the completion of the other. Assume an Alice program that first starts the runtime handling for only the Heartbeat session. Eventually, the shown s7 callback is fired when Alice is ready to fire pong (some time after the preceding handling of ping has finished), leading to the (local, non-blocking) start_link action by Alice to start handling the Request session. Bob may asynchronously send request before or after that point; even if before, Alice consumes the request message only after ping and s7 . • (Right) The handling of an event is postponed until some local condition is fulfilled. Assume an Alice program that starts the runtime handling for both sessions. Eventually, the shown s5 callback is fired when Alice receives request . If the local condition LocalCond is not yet fulfilled, Alice postpones the handling of the request message by deferring the active handler (in this example for 50ms). LocalCond may be set by some arbitrary local computation – or a local event triggered by (e.g.) the ping handler in the other session – either way, our framework does rely on the programmer to ensure the correctness of internal computations/events, as stated earlier. ⬇ 1 global protocol Heartbeat ( role Alice , role Carol ){ 2 ping () from Carol to Alice ; 3 pong () from Alice to Carol ; 4 } ⬇ 1 global protocol Request ( role Alice , role Bob ) { 2 request () from Bob to Alice ; 3 response () from Alice to Bob ; 4 } Figure 10. Two simple protocols for an example multi-session program. ⬇ 1 s7 ( internal , { pong }, Data ) -> 2 gen_alice : send_s7_pong ( CarolPid , Data ), 3 _ = gen_alice2 : start_link ( alice2 , []); 4 { stop , normal , Data }. 5 6 7 ⬇ 1 s5 ( cast , { BobPid , { request }}, Data ) -> 2 case LocalCond of 3 true -> 4 { next_state , s7 , Data , [{ next_event , internal , { response }}]}; 5 _ -> 6 defer ({ BobPid , { request }}, 50), { keep_state , Data } 7 end . Figure 11. Basic inter-session dependencies internal to a local Erlang program: trigger vs. defer Event-driven sessions and progress. The second main facet is that our Erlang sessions are event-driven (ED), rather than the typical ‘multithreaded’ model of \pi -calculi. The key points (in addition to those stated earlier) are that: • The Erlang runtime fires a callback and activates the relevant session only when the expected event has occurred and is ready for consumption. Otherwise sessions are passively suspended, meaning that no session ever actively blocks another session’s callback from firing. • Interleaving of multiple sessions is enacted semantically by the Erlang runtime interleaving the firing of callbacks on different sessions, one by one, as their events occur. That is as opposed to the syntactic interleaving of the typical I/O prefixes within a \pi -calculus process, where a prefix on one session can actively block a prefix on another session from being executed (which could, e.g., cause a deadlock cycle). The above concepts are found in many practical systems (e.g., Erlang, Akka, Java NIO, etc), and have been previously formalised in the setting of (linearly-typed) ED session \pi -calculi ( 33 ; 41 ; 58 ) . A global progress property related to the above points was formally established in the specific setting of 58 . Altogether, (multi-session) progress in our Erlang programs can be understood by considering the combination of these points: (1) our formal result that every distributed MC protocol individually satisfies progress ( Theorems 3.13 and 4.4 ); (2) the characteristics of ED sessions; (3) our assumptions on local computations in the practical programs; and (4) inter-session dependencies within a local program expressed by local computations/events. Some multi-session programs may involve only (1)-(3), e.g., as in some client-server applications that spawn a fully independent session per client; in such cases, the ED framework can effectively transfer global type progress to the multi-session process level directly. Some cases of (4) can also be limited to ensure progress, such as when sessions are strictly chained to spawn and run consecutively, or spawned in a restricted tree topology of parent-child subsessions (as found in systems based on linear logic ( 59 ; 9 ) ). As mentioned, however, our practical framework does rely on the user to ensure the correctness of internal computations/events, including more advanced inter-session dependencies, in full generality. Future work. In future work, we will consider extending our toolchain to support the specification of inter- protocol dependencies via composition constraints in the style of 5 . This will allow ad hoc inter-session dependencies at the process level to instead be expressed at the protocol level . The toolchain can compose such protocols into a single EFSM and generate APIs that safely embed the dependencies correctly by construction, rather than relying on the programmer to express them via local computations as illustrated above. We also plan to investigate formalising the event-driven (ED) concurrency of Erlang’s gen_statem and its correctness properties at the process level; however, it should be noted that Erlang is dynamically typed by default. By contrast, 19 recently proved a formal multi-session progress property for a ‘multithreaded’ session \pi -calculus system based on fair termination (see Section 6 ). There may be connections between their notion of fair termination and our practical condition that callbacks and local computations should eventually terminate: their work may give directions for formalising ED callback termination. 58 established a progress property for an ED \pi -calculus involving multiple sessions (their principles for ED progress are similar to those we described in the earlier paragraph). Earlier works ( 47 ; 22 ) developed multi-session progress properties using additional analysis mechanisms on top of session typing. Appendix C Committing and non-committing sets - full definitions The auxiliary function for committing sets is defined as follows: \begin{array}[]{lll}\Downarrow^{c}\hskip-2.84526pt(\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S},{\color[rgb]{0.5,0.5,0.5}C})=\begin{cases}\mathtt{labels}({\color[rgb]{0,0,1}S})\penalty\ \cup\displaystyle\bigcup_{\mathtt{G}\in\mathtt{types}({\color[rgb]{0,0,1}S})}\hskip-11.38092pt\Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C\cup\{\mathtt{q}\}})&\quad\mathtt{p}\in C{\penalty\ \land\penalty\ \mathtt{q}\not\in C}\\[17.07182pt] \displaystyle\bigcup_{\mathtt{G}\in\mathtt{types}({\color[rgb]{0,0,1}S})}\hskip-11.38092pt\Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})&\quad\textit{otherwise}\end{cases}\\[28.45274pt] \Downarrow^{c}\hskip-2.84526pt(\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c^{\prime}}\mkern 1.0mu}\mathtt{G}_{2},{\color[rgb]{0.5,0.5,0.5}C})\penalty\ =\penalty\ \begin{cases}\Downarrow^{c}\hskip-2.84526pt(\mathtt{G}_{1},{\color[rgb]{0.5,0.5,0.5}C})\penalty\ \penalty\ \cup\Downarrow^{c}\hskip-2.84526pt(\mathtt{G}_{2},{\color[rgb]{0.5,0.5,0.5}C})&c\neq c^{\prime}\hskip 51.21504pt\Downarrow^{c}\hskip-2.84526pt(\mu\mathtt{t}.\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})=\Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})\\ \emptyset&\textit{otherwise}\hskip 36.98866pt\Downarrow^{c}\hskip-2.84526pt(\mathtt{end},{\color[rgb]{0.5,0.5,0.5}C})=\Downarrow^{c}\hskip-2.84526pt(\mathtt{t},{\color[rgb]{0.5,0.5,0.5}C})=\emptyset\end{cases}\end{array} The dual auxiliary function for non-committing sets is defined as follows: \begin{array}[]{lll}\Uparrow^{c}\hskip-2.84526pt(\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S},{\color[rgb]{0.5,0.5,0.5}C})=\begin{cases}\displaystyle\bigcup_{\mathtt{G}\in\mathtt{types}({\color[rgb]{0,0,1}S})}\hskip-11.38092pt\Uparrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C\cup\{\mathtt{q}\}})&\quad\mathtt{p}\in C{\penalty\ \land\penalty\ \mathtt{q}\not\in C}\\[17.07182pt] \mathtt{labels}({\color[rgb]{0,0,1}S})\penalty\ \cup\displaystyle\bigcup_{\mathtt{G}\in\mathtt{types}({\color[rgb]{0,0,1}S})}\hskip-11.38092pt\Uparrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})&\quad\textit{otherwise}\end{cases}\\[28.45274pt] \Uparrow^{c}\hskip-2.84526pt(\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c^{\prime}}\mkern 1.0mu}\mathtt{G}_{2},{\color[rgb]{0.5,0.5,0.5}C})\penalty\ =\penalty\ \begin{cases}\Uparrow^{c}\hskip-2.84526pt(\mathtt{G}_{1},{\color[rgb]{0.5,0.5,0.5}C})\penalty\ \penalty\ \cup\Uparrow^{c}\hskip-2.84526pt(\mathtt{G}_{2},{\color[rgb]{0.5,0.5,0.5}C})&c\neq c^{\prime}\hskip 48.36958pt\Uparrow^{c}\hskip-2.84526pt(\mu\mathtt{t}.\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})=\Uparrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})\\ \emptyset&\textit{otherwise}\hskip 36.98866pt\Uparrow^{c}\hskip-2.84526pt(\mathtt{end},{\color[rgb]{0.5,0.5,0.5}C})=\Uparrow^{c}\hskip-2.84526pt(\mathtt{t},{\color[rgb]{0.5,0.5,0.5}C})=\emptyset\end{cases}\end{array} C.1. Extension using observers committing sets Let \mathtt{G} be an initial type and \mathtt{q}\rightarrowtriangle\mathtt{p}:\,{\color[rgb]{0,0,1}S_{1}}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright\mkern 1.0mu}^{\color[rgb]{1,0,1}c}\,\mathtt{p}\rightarrowtriangle\mathtt{q}:\,{\color[rgb]{0,0,1}S_{2}} in \mathtt{U}(\mathtt{G}) a MC definition in \mathtt{U}(\mathtt{G}) . Fix a special set of labels {\color[rgb]{1,0,0}D} of committing actions for the LHS of MC c by its observer \mathtt{p} . We define the {\color[rgb]{1,0,0}D} -committing set of c as \begin{array}[]{lll}\mathtt{labels}({\color[rgb]{0,0,1}S_{1}}\,\cap\,{\color[rgb]{1,0,0}D})\penalty\ \cup\penalty\ \mathtt{labels}({\color[rgb]{0,0,1}S_{2}})\\ \quad\cup\penalty\ \bigcup_{G\in\mathtt{types}({\color[rgb]{0,0,1}S_{1}}\cap{\color[rgb]{1,0,0}D})}\Downarrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}C\cup\{\mathtt{p}\}})\\ \quad\cup\penalty\ \bigcup_{G\in\mathtt{types}({\color[rgb]{0,0,1}S_{1}}\setminus{\color[rgb]{1,0,0}D})}\Downarrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}C})\\ \quad\cup\penalty\ \bigcup_{G\in\mathtt{types}({\color[rgb]{0,0,1}S_{2}})}\Downarrow^{c}\hskip-2.84526pt(G,{\color[rgb]{0.5,0.5,0.5}C\cup\{\mathtt{p},\mathtt{q}\}})\end{array} where \Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C}) is defined as: \begin{array}[]{lll}\small\Downarrow^{c}\hskip-2.84526pt(\mathtt{p}\rightarrowtriangle\mathtt{q}:\{a_{i}.\mathtt{G}_{i}\}_{i\in I},{\color[rgb]{0.5,0.5,0.5}C})=\\ \qquad\qquad\begin{cases}\bigcup_{i\in I}\{a_{i}\}\penalty\ \cup\Downarrow^{c}\hskip-2.84526pt(G_{i},{\color[rgb]{0.5,0.5,0.5}C\cup\{\mathtt{q}\}})&\mathtt{p}\in C\land\mathtt{q}\not\in C\\ (\bigcup_{i\in I}\{a_{i}\}\cap{\color[rgb]{1,0,0}D})\cup\{\Downarrow^{c}\hskip-2.84526pt(G_{i},{\color[rgb]{0.5,0.5,0.5}C\cup\{\mathtt{q}\}})\penalty\ |\penalty\ a_{i}\in{\color[rgb]{1,0,0}D}\}\cup\{\Downarrow^{c}\hskip-2.84526pt(G_{i},{\color[rgb]{0.5,0.5,0.5}C})\penalty\ |\penalty\ a_{i}\not\in{\color[rgb]{1,0,0}D}\}&otw\end{cases}\\[17.07182pt] \Downarrow^{c}\hskip-2.84526pt(\mu\mathtt{t}.\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})=\Downarrow^{c}\hskip-2.84526pt(\mathtt{G},{\color[rgb]{0.5,0.5,0.5}C})\\[11.38092pt] \Downarrow^{c}\hskip-2.84526pt(\mathtt{t},{\color[rgb]{0.5,0.5,0.5}C})=\Downarrow^{c}\hskip-2.84526pt(\mathtt{end},{\color[rgb]{0.5,0.5,0.5}C})=\emptyset\end{array} The definition of eventual dependency based on {\color[rgb]{1,0,0}D} is as follows: \mathtt{q} eventually depends on \mathtt{p} in \mathtt{G} (wrt {\color[rgb]{1,0,0}D} ), written \mathtt{p}\ll_{\mathtt{G}}\mathtt{q} , if \mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\vec{\ell}}}\penalty\ \mathtt{G}^{\prime} implies \exists a\in{\color[rgb]{1,0,0}D}.\penalty\ \mathtt{p}\mathtt{q}!a\in\vec{\ell}\penalty\ \lor\penalty\ \mathtt{G}^{\prime}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{}\hskip-3.44444pt^{*}}\penalty\ \penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a}}\penalty\ . Appendix D Progress of Global Types: extended definitions and proofs Progress is proved via a number of properties. The principal ones have been discussed in the main text. Here, we give full definitions of all properties needed in the proof of progress. First, in Section D.4 we discuss well-nestedness, an auxiliary property on the structure of MC, preserved by transition. In Section D.5 we prove preservation of awareness and in Section D.6 we discuss preservation of balance. We then elaborate on their role to yield the progress property via an invariant property called coherence in Section D.7 . We finally wrap up the progress property in Section D.8 . Remark 1 (Instance annotations). To facilitate reasoning on the instances of MC on a global type we annotate MC instance with an instance identifier n . This annotation will be used only to prove global properties. The properties non correspondence rely on the non-annotated semantics. D.1. Global types with annotated MC The syntax of global types with annotated MC is defined by the grammar below: \begin{array}[]{lll}\mathtt{G}::=\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S}\mid\mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\,{\color[rgb]{0,0,1}S}\mid\mu\mathtt{t}.\mathtt{G}\mid\mathtt{t}\mid\mathtt{end}\mid\mathtt{q}\rightarrowtriangle\mathtt{p}:{\color[rgb]{0,0,1}S_{1}}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c:\mathtt{p}}\mkern 1.0mu}\mathtt{p}\rightarrowtriangle\mathtt{q}:{\color[rgb]{0,0,1}S_{2}}\mid\mathtt{G}_{1}\mathrel{\mkern 1.0mu\blacktriangleright\mkern 1.0mu}^{{\iota}:\mathtt{p}}_{\mathcal{L},\mathcal{R}}\color[rgb]{0,0,0}\mathtt{G}_{2}\end{array} We annotate MC definitions with a unique MC name c . Active MC are annotated with {\iota}=c,n , which are pairs of MC names and counters n\in\mathbb{N}_{\geq 0} . Since a MC may be in the body of a recursive type, many instances of that MC may be generated upon recursive unfolding. We use {\iota} to identify these instances. For readability, we omit annotations \mathtt{p} , c,n , {\iota} , \mathcal{L} , or \mathcal{R} when not needed. The semantics of global types is defined as a Labelled Transition System over terms \mathtt{G} with labels \ell:=\mathtt{p}\mathtt{q}!a\mid\mathtt{p}\mathtt{q}?a\mid\nu c,n The semantics uses a mapping \Theta from global types and MC names to \mathbb{N}_{\geq 0} , that gives the greatest counter among all active MC c in \mathtt{G} \Theta(\mathtt{G},c)=\mathtt{max}(\{0\}\cup\{n\,|\,\text{$\mathtt{G}$ has active MC with identifier ${c},{n}$}\}) \Theta is used to ensure that active MC are uniquely identified by c,n . \begin{array}[]{cc}\begin{array}[]{cc}\mathtt{p}\rightarrowtriangle\mathtt{q}:\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}!a_{k}}}\penalty\ \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ \penalty\ \penalty\ (k\in I)\penalty\ \penalty\ \mathtt{[Snd]}\\[8.5359pt] \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\mathtt{p}\mathtt{q}?a_{k}}}\penalty\ \mathtt{G}_{k}\penalty\ \penalty\ \penalty\ \mathtt{[Rcv]}\penalty\ \penalty\ \penalty\ \hskip 18.49988pt\frac{\forall i\in I\hskip 16.09991pt\mathtt{G}_{i}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \mathtt{G}^{\prime}_{i}\hskip 16.09991pt\mathtt{p},\mathtt{q}\not\in\mathtt{sbj}(\ell)}{\mathtt{p}\rightarrowtriangle\mathtt{q}:\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \mathtt{p}\rightarrowtriangle\mathtt{q}:\{a_{i}.\mathtt{G}^{\prime}_{i}\}_{i\in I}}\penalty\ \penalty\ \mathtt{[Cont1]}\\[19.91684pt] \frac{\mathtt{G}[\mu\mathtt{t}.\mathtt{G}/\mathtt{t}]\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ {\mathtt{G}^{\prime}}}{\mu\mathtt{t}.\mathtt{G}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ {\mathtt{G}^{\prime}}}\penalty\ \penalty\ \mathtt{[Rec]}\hskip 18.49988pt\penalty\ \penalty\ \frac{\mathtt{G}_{k}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ {\mathtt{G}^{\prime}_{k}}\hskip 16.09991pt\mathtt{q}\not\in\mathtt{sbj}(\ell)\hskip 16.09991pt\forall i\in I\setminus k.\,\mathtt{G}_{i}=\mathtt{G}_{i}^{\prime}}{\mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\{a_{i}.\mathtt{G}_{i}\}_{i\in I}\penalty\ {\color[rgb]{0,0,1}\xrightarrow{\ell}}\penalty\ \mathtt{p}\mathrel{\raisebox{0.56905pt}{\hbox to8.94pt{\vbox to3.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-1.65598pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} \lxSVG@begingroup@{_scopebegin} \lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap} \lx@inpgf@ignorespaces{}{ }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 0 0 L 1.28 1.11 L 3.84 -1.11 L 6.4 1.11 L 7.68 0 L 7.68 0 L 7.7 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{ {{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{5.66763pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 3.49 0 L 0.28 1.88 L 0 0 L 0.28 -1.88 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\mathtt{q}:k\{a_{i}.\mathtt{G}^{\prime}_{i}\}_{i\in I}}\penalty\ \penalty\ \mathtt{[Cont2]}\\[19.91684pt] \hline\cr\\ \end{array}\\ \begin{array}[]{rr}\frac{\Theta(\mathtt{G}_{1}\mathrel{\color[rgb]{1,0,1}\mkern 1.0mu\triangleright^{c:\mathtt{p}}\mkern 1.0mu}\mathtt{G}_{2},c)