Logical Methods in Computer Science
Vol. 13(2:1)2017, pp. 1–57
www.lmcs-online.org

Submitted
Published

Jan. 15, 2016
Apr. 7, 2017

DYNAMIC CHOREOGRAPHIES: THEORY AND IMPLEMENTATION
MILA DALLA PREDA a , MAURIZIO GABBRIELLI b , SAVERIO GIALLORENZO c , IVAN LANESE d ,
AND JACOPO MAURO e
a

b,c,d

e

Department of Computer Science, University of Verona
e-mail address: mila.dallapreda@univr.it
Department of Computer Science and Engineering, University of Bologna/INRIA
e-mail address: {gabbri, sgiallor, lanese}@cs.unibo.it
Department of Informatics, University of Oslo
e-mail address: jacopom@ifi.uio.no

Abstract. Programming distributed applications free from communication deadlocks and
race conditions is complex. Preserving these properties when applications are updated at
runtime is even harder. We present a choreographic approach for programming updatable,
distributed applications. We define a choreography language, called Dynamic InteractionOriented Choreography (DIOC), that allows the programmer to specify, from a global
viewpoint, which parts of the application can be updated. At runtime, these parts may
be replaced by new DIOC fragments from outside the application. DIOC programs are
compiled, generating code for each participant in a process-level language called Dynamic
Process-Oriented Choreographies (DPOC). We prove that DPOC distributed applications
generated from DIOC specifications are deadlock free and race free and that these properties
hold also after any runtime update. We instantiate the theoretical model above into a
programming framework called Adaptable Interaction-Oriented Choreographies in Jolie
(AIOCJ) that comprises an integrated development environment, a compiler from an
extension of DIOCs to distributed Jolie programs, and a runtime environment to support
their execution.

1. Introduction
Programming distributed applications is an error-prone activity. Participants send and
receive messages but, if the application is badly programmed, they may get stuck waiting
for messages that never arrive (communication deadlock), or they may receive messages in
an unexpected order, depending on the speed of the other participants and of the network
(races).
Key words and phrases: Choreographies, Adaptable Systems, Deadlock Freedom.
Supported by the EU EIT Digital project SMAll .
d
Supported by the GNCS group of INdAM via project Logica, Automi e Giochi per Sistemi Auto-adattivi.
e
Supported by the EU project FP7-644298 HyVar: Scalable Hybrid Variability for Distributed, Evolving
Software Systems.
c

l

LOGICAL METHODS
IN COMPUTER SCIENCE

©
DOI:10.23638/LMCS-13(2:1)2017

CC

M. Dalla Preda, M. Gabbrielli, S. Giallorenzo, I. Lanese, and J. Mauro
Creative Commons

2

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

Recently, language-based approaches have been proposed to tackle the complexity of
programming concurrent and distributed applications. These approaches provide high-level
primitives that avoid by construction some of the risks of concurrent programming. Some
renowned examples are the ownership/borrowing mechanisms of Rust [44] and the separate
keyword of SCOOP [41]. In these settings most of the work needed to ensure a correct
behaviour is done by the language compiler and runtime support. The use of these languages
requires a conceptual shift from traditional ones, but reduces times and costs of development,
testing, and maintenance by avoiding some of the most common programming errors.
We propose an approach based on choreographic programming [12, 13, 30, 47, 34] following
a similar philosophy. A choreography is a global description of a distributed application
expressed as the composition of the expected interactions between its components. Based
on such an abstraction, we present high-level primitives that avoid some of the main errors
linked to programming communication-centred concurrent and distributed applications that
can be updated at run time.
For an informal introduction of our approach, let us consider a simple application where
a Buyer asks the price of some product to a Seller.
priceReq : Buyer(prod) → Seller(order);
2 order price@Seller = getPrice(order);
3 offer : Seller(order price) → Buyer(prod price)
1

A unique choreographic program describes the behaviour of multiple participants, here
the Buyer and the Seller. The first line specifies that the Buyer sends, along channel
priceReq, the name of the desired product prod to the Seller, which stores it in its local
variable order. At Line 2, the Seller computes the price of the product with function
getPrice. Finally, at Line 3 the Seller sends the computed price to the Buyer on channel
offer . The Buyer stores the value in its local variable prod price.
Choreographic languages focus on describing message-based interactions between distributed participants. As shown by the example, the distinctive feature of choreographies is
that communications are atomic entities, i.e., not split into send and receive actions. This
makes impossible to write programs with common errors of concurrent and distributed applications like deadlocks or race conditions. However, a choreographic description is not directly
executable. Indeed, choreographies describe atomic interactions from a global point of view
whilst executable programs are written in lower level languages (like Java or C) that support
only local behaviours and communication/synchronisation primitives such as message send
and message receive. Hence, to run a choreographic description, we have to compile it into a
set of lower level programs. The correct compilation of choreographic descriptions is one of
the main challenges of choreographic languages, yet the ease of development and the strong
guarantees of deadlock and race freedom make it a worth endeavour.
In this work, we take this challenge one step further: we consider updatable distributed
applications whose code can change dynamically, i.e., while the application is running. In
particular, the applications we consider can integrate external code at runtime. Such a
feature, tricky in a sequential setting and even more in a distributed one, has countless
uses: to deal with emergency requirements, to cope with rules and requirements depending
on contextual properties or to improve and specialise the application to user preferences.
We propose a general mechanism to structure application updates. Inside applications, we
delimit blocks of code, called scopes, that may be dynamically replaced by new blocks of

DYNAMIC CHOREOGRAPHIES

3

code, called updates. Updates are loosely related to scopes: it is not necessary to know the
details of the behaviour of updates when writing scopes, and updates may be written while
applications are running.
To illustrate our approach, let us consider the previous example and let us suppose that
we would like to introduce new commercial offers at runtime, e.g., to provide a discount
on the computed prices. Since we want to be able to change how prices are computed, we
enclose Lines 2–3 of the example within a scope, as shown below.
priceReq : Buyer(prod) → Seller(order);
scope @Seller{
3
order price@Seller = getPrice(order);
4
offer : Seller(order price) → Buyer(prod price)
5 }

1

2

In essence, a scope is a delimiter that defines which part of the application can be updated.
Each scope identifies a coordinator of the update, i.e., the participant entitled to ensure that
either none of the participants updates, or they all apply the same update. In the example
above, the coordinator of the update is the Seller (Line 2).
Since now the code includes a scope, we can introduce runtime updates. Let us assume
that the Seller issued a fidelity card to some frequent customers and (s)he wants to update
the application to let Buyers insert their fidelity card to get a discount. The update in
Figure 1 answers this business need. At runtime, if the Seller (which is the coordinator of
the update) applies the update in Figure 1, the code of the update replaces the scope. When
this new code executes, the Buyer sends his/her card id to the Seller. If the card id is
valid, the Seller issues a 10% discount on the price of the selected good, otherwise it reports
the standard price to the Buyer.
We remark that expressing the behaviour described above using lower level languages
that lack a dedicated support for distributed runtime updates (e.g., Java, C, etc.) is extremely
error prone. For instance, in the example above, let us consider the case in which the Buyer
is updated first and it starts the execution whilst the Seller has not been updated yet. The
Buyer waits for a message from the Seller on channel cardReq, whilst the Seller sends a
message on channel offer . Thus, the application is deadlocked. Furthermore, in our setting
the available updates may change at any time, posing an additional challenge. To avoid
1
2
3
4
5
6
7
8
9

cardReq : Seller(null) → Buyer( );
card id@Buyer = getInput();
cardRes : Buyer(card id) → Seller(buyer id);
if isValid(buyer id)@Seller {
order price@Seller = getPrice(order) ∗ 0.9
} else {
order price@Seller = getPrice(order)
};
offer : Seller(order price) → Buyer(prod price)
Figure 1: Fidelity Card Update.

4

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

errors, participants must select the same update and, since updates appear and disappear at
runtime, they must also be able to retrieve the same selected update.
Since at choreographic level updates are applied atomically to all the involved participants, these problems cannot arise if both the original application and the updates are
described as choreographies. However, to execute our choreographic specifications we need
to provide a correct compilation from choreographies to lower level, executable programs.
Such task is very challenging and, in particular, we need to make sure that our compilation
generates correct behaviours that avoid inconsistencies on updates.
Contributions. In this paper, we present a correctness-by-construction approach to solve the
problem of dynamic updates of distributed applications. We provide a general solution that
comprises:
• the definition of a Dynamic Interaction-Oriented Choreography language, called DIOC, to
program distributed applications and supporting runtime code update (§ 2);
• the definition of a Dynamic Process-Oriented Choreography language, called DPOC.
DPOCs are based on standard send and receive primitives but they are tailored to program
updatable systems. We introduce DPOCs to describe implementations corresponding to
DIOCs. (§ 3);
• the definition of a behaviour-preserving projection function to compile DIOCs into DPOCs
(§ 4);
• the proof of the correctness of the projection function (§ 7). Correctness is guaranteed
even in a scenario where the set of available updates dynamically changes, at any moment
and without notice;
• one instantiation of our theory into a development framework for adaptive distributed
applications called AIOCJ (§ 8). In AIOCJ updates are embodied into adaptation rules,
whose application is not purely non-deterministic (as in DIOCs), but depends on the
state of the system and of its environment. AIOCJ comprises an Integrated Development
Environment, a compiler from choreographies to executable programs, and a runtime
environment to support their execution and update.
This paper integrates and extends material from [18], which outlines the theoretical aspects,
and [19], which describes the AIOCJ framework. Main extensions include the full semantics
of DIOC and DPOC, detailed proofs and technical definitions, and a thorough description
of the example. Furthermore, both the presentation and the technical development have
been deeply revised and refined.
2. Dynamic Interaction-Oriented Choreographies
In this section we introduce the syntax of DIOCs, we illustrate the constructs of the DIOC
language with a comprehensive example, and we finally present the semantics of DIOCs.
2.1. DIOC Syntax. DIOCs rely on a set of Roles, ranged over by R, S, . . . , to identify the
participants in the choreography. We call them roles to highlight that they have a specific
duty in the choreography. Each role has its local state.
Roles exchange messages over public channels, also called operations, ranged over by o.
We denote with Expr the set of expressions, ranged over by e. We deliberately do not give a
formal definition of expressions and of their typing, since our results do not depend on it.
We only require that expressions include at least values, belonging to a set Val ranged over

DYNAMIC CHOREOGRAPHIES

5

by v, and variables, belonging to a set Var ranged over by x, y, . . . . We also assume a set of
boolean expressions ranged over by b.
The syntax of DIOC processes, ranged over by I, I 0 , . . ., is defined as follows:
I ::=
|
|
|
|

o : R(e) → S(x)
I; I 0
I|I 0
x@R = e
1

(interaction)
(sequence)
(parallel)
(assignment)
(inaction)

|
|
|
|

0
if b@R {I} else {I 0 }
while b@R {I}
scope @R {I}

(end)
(conditional)
(while)
(scope)

Interaction o : R(e) → S(x) means that role R sends a message on operation o to role S (we
require R 6= S). The sent value is obtained by evaluating expression e in the local state of R
and it is then stored in the local variable x of S. Processes I; I 0 and I|I 0 denote sequential
and parallel composition, respectively. Assignment x@R = e assigns the evaluation of
expression e in the local state of R to its local variable x. The empty process 1 defines
a DIOC that can only terminate. 0 represents a terminated DIOC. It is needed for the
definition of the operational semantics and it is not intended to be used by the programmer.
We call initial a DIOC process where 0 never occurs. The conditional if b@R {I} else {I 0 }
and the iteration while b@R {I} are guarded by the evaluation of the boolean expression
b in the local state of R.The construct scope @R {I} delimits a subterm I of the DIOC
process that may be updated in the future. In scope @R {I}, role R is the coordinator
of the update: it ensures that either none of the participants update, or they all apply the
same update.
A Running Example. We report in Figure 2 a running example of a DIOC process that
extends the one presented in the Introduction: the example features a Buyer that orders
a product from a Seller, and a Bank that supports the payment from the Buyer to the
Seller. The DIOC process describes the behaviour of all of them. In this sense, the DIOC
implements a protocol they agreed upon to integrate their business. The DIOC protocol
also interacts with functionalities that are only available at the premises of some of the
participants (for instance, the function getPrice is provided by the Seller IT system and
may be only locally available). For this reason, it is important that the execution of the
DIOC is distributed across the participants.
At Lines 1–2 the Buyer initialises its local variables price ok and continue. These
variables control the while loop used by the Buyer to ask the price of some product to the
Seller. The loop execution is controlled by the Buyer, but it impacts also the behaviour
of the Seller. We will see in § 4 that this is done using automatically generated auxiliary
communications. A similar approach is used to manage conditionals. At Line 4, the
Buyer takes the name of the product from the user with function getInput, which models
interaction with the user, and proceeds to send it to the Seller on operation priceReq (Line
5). The Seller computes the price of the product calling the function getPrice (Line 7)
and, via operation offer , it sends the price to the Buyer (Line 8), that stores it in a local
variable prod price. These last two operations are performed within a scope and therefore
they can be updated at runtime to implement some new business policies (e.g., discounts).
At Lines 10–12 the Buyer checks whether the user is willing to buy the product, and, if
(s)he is not interested, whether (s)he wants to ask prices for other products. If the Buyer
accepts the offer of the Seller, the Seller sends to the Bank the payment details (Line 16),

6

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

price ok@Buyer = false;
continue@Buyer = true;
while( !price ok and continue )@Buyer{
prod@Buyer = getInput();
priceReq : Buyer(prod) → Seller(order);
scope @Seller{
order price@Seller = getPrice(order);
offer : Seller(order price) → Buyer(prod price)
};
price ok@Buyer = getInput();
if ( !price ok )@Buyer{
continue@Buyer = getInput()
}
};
if ( price ok )@Buyer{
payReq : Seller( payDesc(order price) ) → Bank(desc);
scope @Bank{
pay : Buyer( payAuth(prod price) ) → Bank(auth)
};
payment ok@Bank = makePayment(desc, auth);
if ( payment ok )@Bank{
conf irm : Bank(null) → Seller( )
|
conf irm : Bank(null) → Buyer( )
} else {
abort : Bank(null) → Buyer( )
}
}
Figure 2: DIOC process for Purchase Scenario.

computed using function payDesc. Next, the Buyer authorises the payment via operation
pay, computing the payment authorisation form using function payAuth. Since the payment
may be critical for security reasons, the related communication is enclosed in a scope (Lines
17–19), thus allowing the introduction of more refined procedures later on. After the scope
successfully terminates, at Line 20 the Bank locally executes the actual payment by calling
function makePayment. The function makePayment abstracts an invocation to the Bank IT
system. We show in § 8 that, using functions, one can integrate existing service-oriented
software into a choreographic program.
Finally, the Bank acknowledges the payment to the Seller and the Buyer in parallel
(Lines 22–24). If the payment is not successful, the failure is notified explicitly only to the
Buyer. Note that at Lines 1–2 the annotation @Buyer means that the variables price ok
and continue belong to the Buyer. Similarly, at Line 3, the annotation @Buyer means
that the guard of the while loop is evaluated by the Buyer. The term @Seller at Line 6 is
part of the scope construct and indicates the Seller as coordinator of the update.

DYNAMIC CHOREOGRAPHIES

7

2.2. Annotated DIOCs and their Semantics. In the remainder of the paper, we define
our results on an annotated version of the DIOC syntax.Annotations are numerical indexes
i ∈ N assigned to DIOC constructs. We only require indexes to be distinct. Any annotation
that satisfies this requirement provides the same result. Indeed, programmers do not need
to annotate DIOCs: the annotation with indexes is mechanisable and can be performed
by the language compiler1. Indexes are used both in the proof of our results and in the
projection to avoid interferences between different constructs. From now on we consider
only well-annotated DIOCs, defined as follows.
Definition 2.1 (Well-annotated DIOC). Annotated DIOC processes are obtained by
indexing every interaction, assignment, conditional, while loop, and scope in a DIOC process
with a positive natural number i ∈ N, resulting in the following grammar:
I ::=
|
|
|
|

i: o : R(e) → S(x)
I; I 0
I|I 0
i: x@R = e
1

|
|
|
|

0
i: if b@R {I} else {I 0 }
i: while b@R {I}
i: scope @R {I}

A DIOC process is well annotated if all its indexes are distinct.
DIOC processes do not execute in isolation: they are equipped with a global state Σ
and a set of available updates I, i.e., a set of DIOCs that may replace scopes. Set I may
change at runtime. A global state Σ is a map that defines the value v of each variable x
in a given role R, namely Σ : Roles × Var → Val . The local state of role R is denoted as
ΣR : Var → Val and it verifies that ∀x ∈ Var : Σ(R, x) = ΣR (x). Expressions are always
evaluated by a given role R: we denote the evaluation of expression e in local state ΣR as
[[e]]ΣR . We assume that [[e]]ΣR is always defined (e.g., an error value is given as a result if
evaluation is not possible) and that for each boolean expression b, [[b]]ΣR is either true or
false.
Remark 2.2. The above assumption on expressions is needed for our results. To satisfy
it, when programming, one should prevent runtime errors and notify abnormal events to
partners using normal constructs to guarantee error management or smooth termination
(see e.g., Lines 21–26 in Figure 2). A more elegant way to deal with errors would be to
include in the language well-known constructs, such as try-catch, which are however left as
future work. This could be done by adapting the ideas presented in [9].
Definition 2.3 (DIOC systems). A DIOC system is a triple hΣ, I, Ii denoting a DIOC
process I equipped with a global state Σ and a set of updates I.
Definition 2.4 (DIOC systems semantics). The semantics of DIOC systems is defined
as the smallest labelled transition system (LTS) closed under the rules in Figure 3, where
symmetric rules for parallel composition have been omitted.
The rules in Figure 3 describe the behaviour of a DIOC system by induction on the
structure of its DIOC process, with a case analysis on its topmost operator. We use µ to
range over labels. The possible values for µ are described below.
µ ::=
|
|

o : R(v) → S(x) (interaction)
I
(update)
I
(change updates)

1In fact, the AIOCJ compiler implements such a feature.

|
|
|

τ
(silent)
no-up
(no update)
√
(termination)

8

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

[[e]]ΣR = v

bDIOC |Interaction e

o:R(v)→S(x)

hΣ, I, i: o : R(e) → S(x)i −−−−−−−−→ hΣ, I, i: x@S = vi
[[e]]ΣR = v

bDIOC |Assign e
τ
hΣ, I, i: x@R = ei −
→ hΣ[v/x, R], I, 1i
√
µ
hΣ, I, Ii −
→ hΣ, I0 , I 0 i µ 6=
bDIOC |Sequence e
µ
hΣ, I, I; J i −
→ hΣ, I0 , I 0 ; J i
√

µ

hΣ, I, Ii −
→ hΣ, I, I 0 i

hΣ, I, J i −
→ hΣ, I, J 0 i
µ

hΣ, I, I; J i −
→ hΣ, I, J 0 i
µ

hΣ, I, Ii −
→ hΣ, I0 , I 0 i µ 6=
µ

hΣ, I, I k J i −
→

hΣ, I0 , I 0

√

k Ji

bDIOC |Parallel e

√

√

hΣ, I, Ii −
→ hΣ, I, I 0 i

hΣ, I, J i −
→ hΣ, I, J 0 i
√

hΣ, I, I k J i −
→

hΣ, I, I 0

k

bDIOC |Seq-end e

J 0i

[[b]]ΣR = true

bDIOC |Par-end e

τ

bDIOC |If-then e

τ

bDIOC |If-else e

hΣ, I, i: if b@R {I} else {I 0 }i −
→ hΣ, I, Ii
[[b]]ΣR = false
hΣ, I, i: if b@R {I} else {I 0 }i −
→ hΣ, I, I 0 i
[[b]]ΣR = true
τ

hΣ, I, i: while b@R {I}i −
→ hΣ, I, I; i: while b@R {I}i
[[b]]ΣR = false
τ

hΣ, I, i: while b@R {I}i −
→ hΣ, I, 1i
roles(I 0 ) ⊆ roles(I) I 0 ∈ I

bDIOC |While-exit e

connected(I 0 ) freshIndexes(I 0 )
I0

hΣ, I, i: scope @R {I}i −→

hΣ, I, I 0 i

no-up

hΣ, I, i: scope @R {I}i −−−−→ hΣ, I, Ii
bDIOC |End e

√

hΣ, I, 1i −
→ hΣ, I, 0i

bDIOC |While-unfold e

I0

hΣ, I, Ii −
→

bDIOC |Up e

bDIOC |NoUp e

hΣ, I0 , Ii

bDIOC |Change-Updates e

Figure 3: Annotated DIOC system semantics.
Rule bDIOC |Interaction e executes a communication from R to S on operation o, where R
sends to S the value v of an expression e. The communication reduces to an assignment
that inherits the index i of the interaction. The assignment stores value v in variable x
of role S. Rule bDIOC |Assign e evaluates the expression e in the local state ΣR and stores
the resulting value v in the local variable x in role R ([v/x, R] represents the substitution).

DYNAMIC CHOREOGRAPHIES

9

roles(i: o : R(e) → S(x)) = {R, S}
roles(1) = roles(0) = ∅
roles(i: x@R = e) = {R}
roles(I; I 0 ) = roles(I|I 0 ) = roles(I) ∪ roles(I 0 )
roles(i: if b@R {I} else {I 0 }) = {R} ∪ roles(I) ∪ roles(I 0 )
roles(i: while b@R {I}) = roles(i: scope @R {I}) = {R} ∪ roles(I)
Figure 4: Auxiliary function roles.
Rule bDIOC |Sequence e executes a step in the first process of a sequential composition, while
Rule bDIOC |Seq-end e acknowledges the termination of the first process, starting the second
one. Rule bDIOC |Parallel e allows a process in a parallel composition to compute, while Rule
bDIOC |Par-end e synchronises the termination of two parallel processes. Rules bDIOC |If-then e
and bDIOC |If-else e evaluate the boolean guard of a conditional, selecting the “then” and
the “else” branch, respectively. Rules bDIOC |While-unfold e and bDIOC |While-exit e correspond
respectively to the unfolding of a while loop when its condition is satisfied and to its
termination otherwise. Rule bDIOC |Up e and Rule bDIOC |NoUp e deal with updates: the
former applies an update, while the latter allows the body of the scope to be executed
without updating it. More precisely, Rule bDIOC |Up e models the application of the update
I 0 to the scope scope @R {I} which, as a result, is replaced by the DIOC process I 0 .
In the conditions of the rule, we use the function roles and the predicates connected and
freshIndexes. Function roles(I), defined in Figure 4, computes the roles of a DIOC process I.
The condition of the rule requires that the roles of the update are a subset of the roles of
the body of the scope. Predicate connected(I 0 ) holds if I 0 is connected. Connectedness is a
well-formedness property of DIOCs and is detailed in § 6. Roughly, it ensures that roles
involved in a sequential composition have enough information to enforce the correct sequence
of actions. Predicate freshIndexes(I 0 ) holds if all indexes in I 0 are fresh with respect to all
indexes already present in the target DIOC2. This is needed to avoid interferences between
communications inside the update and communications in the original DIOC. This problem
is discussed in more details in § 4, Example 4.3. Rule bDIOC |NoUp e, used when no update is
applied, removes the scope boundaries and starts the execution of the body of the scope.
Rule bDIOC |End e terminates the execution of an empty process. Rule bDIOC |Change-Updates e
allows the set I of available updates to change. This rule is always enabled and models the
fact that the set of available updates is not controlled by the system, but by the external
world: the set of updates can change at any time, the system cannot forbid or delay these
changes, and the system is not notified when they happen. Label I is needed to make the
changes to the set of available updates observable (cf. Definition 7.1).
Remark 2.5. Whether to update a scope or not, and which update to apply if many are
available, is completely non-deterministic. We have adopted this view to maximise generality.
However, for practical applications it is also possible to reduce the non-determinism using
suitable policies to decide when and whether a given update applies. One of such policies is
defined in AIOCJ (see § 8).
2We do not give a formal definition of freshIndexes(I 0 ) to keep the presentation simple. However, freshness

of indexes can be formally ensured using restriction as in π-calculus [46].

10

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

We can finally provide the definition of DIOC traces and weak DIOC traces, which
we use to express our results of behavioural correspondence between DIOCs and DPOCs.
Intuitively, in DIOC traces all the performed actions are observed, whilst in weak DIOC
traces silent actions τ are not visible.
Definition 2.6 (DIOC traces). A (strong) trace of a DIOC system hΣ1 , I1 , I1 i is a sequence
(finite or infinite) of labels µ1 , µ2 , . . . such that there is a sequence of DIOC system transitions
µ1
µ2
hΣ1 , I1 , I1 i −→ hΣ2 , I2 , I2 i −→ . . . .
A weak trace of a DIOC system hΣ1 , I1 , I1 i is a sequence of labels µ1 , µ2 , . . . obtained
by removing all silent labels τ from a trace of hΣ1 , I1 , I1 i.
3. Dynamic Process-Oriented Choreographies
In this section we define the syntax and semantics of DPOCs, the target language of our
projection from DIOCs. We remind that DIOCs are not directly executable since their basic
primitives describe distributed interactions. On the contrary, mainstream languages like Java
and C, used for implementation, describe distributed computations using local behaviours
and communication/synchronisation primitives, such as message send and message receive. In
order to describe implementations corresponding to DIOCs we introduce the DPOC language,
a core language based on this kind of primitives, but tailored to program updatable systems.
Indeed, differently from DIOC constructs, DPOC constructs are locally implementable in
any mainstream language. In AIOCJ (see § 8) we implement the DPOC constructs in the
Jolie [36] language.
3.1. DPOC syntax. DPOCs include processes, ranged over by P, P 0 , . . ., describing the
behaviour of participants. (P, Γ)R denotes a DPOC role named R, executing process P in a
local state Γ. Networks, ranged over by N , N 0 , . . ., are parallel compositions of DPOC roles
with different names. DPOC systems, ranged over by S, are DPOC networks equipped with
a set of updates I, namely pairs hI, N i.
DPOCs, like DIOCs, feature operations o. Here we call them programmer-specified
operations to mark the difference with respect to auxiliary operations, ranged over by o∗ .
We use o? to range over both programmer-specified and auxiliary operations. Differently
from communications on programmer-specified operations, communications on auxiliary
operations have no direct correspondent at the DIOC level. Indeed, we introduce auxiliary
operations in DPOCs to implement the synchronisation mechanisms needed to realise the
global constructs of DIOCs (conditionals, while loops, and scopes) at DPOC level.
Like DIOC constructs, also DPOC constructs are annotated using indexes. However,
in DPOCs we use two kinds of indexes: normal indexes i ∈ N and auxiliary indexes of the
forms iT , iF , i? , and iC where i ∈ N. Auxiliary indexes are introduced by the projection,
described in § 4, and are described in detail there. We let ι range over DPOC indexes.
In DPOCs, normal indexes are also used to prefix the operations in send and receive
primitives3. Thus, a send and a receive can interact only if they are on the same operation
and they are prefixed by the same normal index. This is needed to avoid interferences
3In principle, one may use just indexes and drop operations. However, explicit operations are the standard

for communication-based systems, in particular in the area of Web Services, as they come handy to specify
and to debug such systems.

DYNAMIC CHOREOGRAPHIES

11

between concurrent communications, in particular when one of them comes from an update.
We describe in greater detail this issue in § 4, Example 4.3.
The syntax of DPOCs is the following.
P ::=
|
|
|
|
|

ι: i.o? : x from R
ι: i.o? : e to R
i: i.o∗ : X to R
P;P0
P | P0
ι: x = e
X ::=

no

(receive)
(send)
(send-update)
(sequence)
(parallel)
(assignment)
|

P

|
|
|
|
|
|

1
(inaction)
0
(end)
i: if b {P } else {P 0 }
(conditional)
i: while b {P }
(while)
i: scope @R {P } roles {S} (scope-coord)
i: scope @R {P }
(scope)
N ::=

(P, Γ)R

|

N k N0

DPOC processes include receive action ι : i.o? : x from R on a specific operation
(either programmer-specified or auxiliary) of a message from role R to be stored in
variable x, send action ι: i.o? : e to R of the value of an expression e to be sent to role
R, and higher-order send action i : i.o∗ : X to R of the higher-order argument X to be
sent to role R. Here X may be either a DPOC process P , which is the new code for a
scope in R, or a token no, notifying that no update is needed. P ; P 0 and P |P 0 denote
the sequential and parallel composition of P and P 0 , respectively. Processes also feature
assignment ι : x = e of the value of expression e to variable x, the process 1, that can
only successfully terminate, and the terminated process 0. DPOC processes also include
conditionals i: if b {P } else {P 0 } and loops i: while b {P }. Finally, there are two constructs
for scopes. Construct i: scope @R {P } roles {S} defines a scope with body P and set of
participants S, and may occur only inside role R, which acts as coordinator of the update.
The shorter version i: scope @R {P } is used instead inside the code of some role R1 , which
is not the coordinator R of the update. In fact, only the coordinator R needs to know the
set S of involved roles to be able to send to them their updates.
i.o?

3.2. DPOC semantics. DPOC semantics is defined in two steps: we define the semantics
of DPOC roles first, and then we define how roles interact giving rise to the semantics of
DPOC systems.
Definition 3.1 (DPOC roles semantics). The semantics of DPOC roles is defined as the
smallest LTS closed under the rules in Figure 5, where we report the rules dealing with
computation, and Figure 6, in which we define the rules related to updates. Symmetric rules
for parallel composition have been omitted.
DPOC role semantics. We use δ to range over labels. The possible values for δ are as follows:
δ ::= i.o? hvi@S : R
| i.o∗ hXi@S : R
|I
|τ

(send) | i.o? (x ← v)@S : R
(send-update) | i.o∗ (← X)@S : R
(update) | no-up
√
(silent) |

(receive)
(receive-update)
(no-update)
(termination)

12

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

[[e]]Γ = v

bDPOC |One e

√

τ

(1, Γ)R −
→ (0, Γ)R

(ι: x = e, Γ)R −
→ (1, Γ[v/x])R

bDPOC |Assign e

[[e]]Γ = v
bDPOC |Send e
? hvi@S:R

i.o
ι: i.o? : e to S, Γ R −−−−−−−→ (1, Γ)R
ι:

i.o?

 i.o? (x←v)@S:R
: x from S, Γ R −−−−−−−−−−→ (ι: x = v, Γ)R

bDPOC |Recv e

bDPOC |Send-Up e
? hXi@S:R

i.o
i: i.o? : X to S, Γ R −−−−−−−−→ (1, Γ)R
√
δ
(P, Γ)R →
− (P 0 , Γ0 )R δ 6=
bDPOC |Sequence e
δ
0
0
(P ; Q, Γ)R →
− (P ; Q, Γ )R
√

δ

(P, Γ)R −
→ (P 0 , Γ)R

(Q, Γ)R →
− (Q0 , Γ0 )R
δ

(P ; Q, Γ)R →
−

(Q0 , Γ0 )

δ

(P, Γ)R →
− (P 0 , Γ0 )R
δ

(P | Q, Γ)R →
−

(P 0

(P, Γ)R −
→ (P 0 , Γ)R

√

(P | Q, Γ)R −
→

R

δ 6=
Q, Γ0 )

|

√

√

√
bDPOC |Parallel e
R

(Q, Γ)R −
→ (Q0 , Γ)R
(P 0

|

Q0 , Γ)

bDPOC |Par-end e

R

[[b]]Γ = true
τ

bDPOC |If-Then e

τ

bDPOC |If-Else e

(i: if b {P } else {P 0 }, Γ)R −
→ (P, Γ)R
[[b]]Γ = false
(i: if b {P } else {P 0 }, Γ)R −
→ (P 0 , Γ)R
[[b]]Γ = true
τ

(i: while b {P }, Γ)R −
→ (P ; i: while e {P }, Γ)R
[[b]]Γ = false
τ

bDPOC |Seq-end e

(i: while b {P }, Γ)R −
→ (1, Γ)R

bDPOC |While-unfold e

bDPOC |While-exit e

Figure 5: DPOC role semantics. Computation rules. (Update rules in Figure 6)
The semantics is in the early style. Rule bDPOC |Recv e receives a value v from role S
and assigns it to local variable x of R. Similarly to Rule bDIOC |Interact e (see Figure 3), the
reception reduces to an assignment that inherits the index i from the receive primitive.
Rules bDPOC |Send e and bDPOC |Send-Up e execute send and higher-order send actions,
respectively. Send actions evaluate expression e in the local state Γ. Rule bDPOC |One e
terminates an empty process. Rule bDPOC |Assign e executes an assignment ([v/x] represents
the substitution of value v for variable x). Rule bDPOC |Sequence e executes a step in the first
process of a sequential composition, while Rule bDPOC |Seq-end e acknowledges the termination
of the first process, starting the second one. Rule bDPOC |Parallel e allows a process in a

DYNAMIC CHOREOGRAPHIES

roles(I) ⊆ S

13

freshIndexes(I) connected(I)

bDPOC |Lead-Up e

I

(i: scope @R {P } roles {S}, Γ)R −
→
Q
i: i.sb∗i : π(I, Rj ) to Rj ; π(I, R);
Rj ∈S\{R}

!
Q

i:

Rj ∈S\{R}

i.se∗i

: from Rj , Γ
R

bDPOC |Lead-NoUp e

no-up

(i: scope @R {P } roles {S}, Γ)R −−−−→
Q
Q
i: i.sb∗i : no to Rj ; P ;
Rj ∈S\{R}

Rj ∈S\{R}

0
i.sb∗
i (←P )@S:R

!
i:

i.se∗i

R

bDPOC |Up e
0

(i: scope @S {P }, Γ)R −−−−−−−−−−−→ (P ; i:
i.sb∗
i (←no)@S:R

: from Rj , Γ

(i: scope @S {P }, Γ)R −−−−−−−−−−−→ (P ; i:

i.se∗i

i.se∗i

: ok to S, Γ)R
bDPOC |NoUp e

: ok to S, Γ)R

Figure 6: DPOC role semantics. Update rules. (Computation rules in Figure 5)
parallel composition to compute, while Rule bDPOC |Par-end e synchronises the termination of
two parallel processes. Rules bDPOC |If-then e and bDPOC |If-else e select the “then” and the
“else” branch in a conditional, respectively. Rules bDPOC |While-unfold e and bDPOC |While-exit e
model respectively the unfolding and the termination of a while loop.
The rules reported in Figure 6 deal with code updates. Rules bDPOC |Lead-Up e and
DPOC
b
|Lead-NoUp e specify the behaviour of the coordinator R of the update, respectively
when an update is performed and when no update is performed. In particular, R nondeterministically selects whether to update or not and, in the first case, which update to
apply. The coordinator communicates the selection to the other roles in the scope using
operations sb∗i . The content of the message is either the new code that the other roles need to
execute, if the update is performed, or a token no, if no update is applied. Communications
on operations sb∗i also ensure that no role starts executing the scope before the coordinator
has selected whether to update or not. The communication is received by the other roles
using Rule bDPOC |Up e if an update is selected and Rule bDPOC |NoUp e if no update is selected.
Similarly, communications on se∗i ensure that the updated code has been completely executed
before any role can proceed to execute the code that follows the scope in its original DP OC
process. Communications on se∗i carry no relevant data: they are used for synchronisation
purposes only.
As already discussed, Rule bDPOC |Lead-Up e models the fact that the coordinator R of
the update non-deterministically selects an update I. The premises of Rule bDPOC |Lead-Up e
are similar to those of Rule bDIOC |Up e (see Figure 3). Function roles is used to check that
the roles in I are included in the roles of the scope. Freshness of indexes is checked by
predicate freshIndexes, and well formedness of I by predicate connected (formally defined
later on, in Definition 6.2 in § 6). In particular, the coordinator R generates the processes
to be executed by the roles in S using the process-projection function π (detailed in § 4).
More precisely, π(I, Ri ) generates the code for role Ri . The processes π(I, Ri ) are sent via
auxiliary higher-order communications on sb∗i to the roles that have to execute them. These

14

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

communications also notify the other roles that
Q they can start executing the new code. Here,
and in the remainder of the paper, we define
Q Ri ∈S Pi as the parallel composition of DPOC
processes Pi for Ri ∈ S. We assume that
binds more tightly than sequential composition.
After the communication of the updated code to the other participants, R starts its own
updated code π(I, R). Finally, auxiliary communications se∗i are used to synchronise the end
of the execution of the update (here denotes a fresh variable to store the synchronisation
message ok). Rule bDPOC |Lead-NoUp e defines the behaviour of the coordinator R when no
update is applied. In this case, R sends a token no to the other involved roles, notifying
them that no update is applied and that they can start executing their original code. End
of scope synchronisation is the same as that of Rule bDPOC |Lead-Up e. Rules bDPOC |Up e and
bDPOC |NoUp e define the behaviour of the other roles involved in the scope. The scope waits
for a message from the coordinator. If the content of the message is no, the body of the
scope is executed. Otherwise, the content of the message is a process P 0 which is executed
instead of the body of the scope.
We highlight the importance of the coordinator R. Since the set of updates may change
at any moment, we need to be careful to avoid that the participants in the scope get code
projected from different updates. Given that only role R obtains and delivers the new code,
one is guaranteed that all the participants receive their projection of the same update.
DPOC system semantics.
Definition 3.2 (DPOC systems semantics). The semantics of DPOC systems is defined as
the smallest LTS closed under the rules in Figure 7. Symmetric rules for parallel composition
have been omitted.
We use η to range over DPOC systems labels. The possible values of η are as follows:
η ::= o? : R(v) → S(x)
(interaction)
| o∗ : R(X) → S()
(interaction-update)
| δ
(role label)
DPOC
DPOC
Rules b
|Lift e and b
|Lift-Up e lift role transitions to the system level. Rule
bDPOC |Lift-Up e also checks that the update I belongs to the set of currently available updates
I. Rule bDPOC |Synch e synchronises a send with the corresponding receive, producing an
interaction. Rule bDPOC |Synch-Up e is similar, but it deals with higher-order interactions. Note
that Rules bDPOC |Synch e and bDPOC |Synch-Up e remove the prefixes from DPOC operations
in transition labels. The labels of these transitions store the information on the occurred
communication: label o? : R1 (v) → R2 (x) denotes an interaction on operation o? from role
R1 to role R2 where the value v is sent by R1 and then stored by R2 in variable x. Label
o∗ : R1 (X) → R2 () denotes a similar interaction, but concerning a higher-order value X,
which can be either the code used in the update or a token no if no update is performed. No
receiver variable is specified, since the received value becomes part of the code of the receiving
process. Rule bDPOC |Ext-Par e allows a network inside a parallel composition to compute.
Rule bDPOC |Ext-Par-End e synchronises the termination of parallel networks. Finally, Rule
bDPOC |Change-Updates e allows the set of updates to change arbitrarily.
We now define DPOC traces and weak DPOC traces, which we later use, along with
DIOC traces and weak DIOC traces, to define our result of correctness.

DYNAMIC CHOREOGRAPHIES

δ

N →
− N0

δ 6= I

δ

hI, N 0 i

hI, N i →
−

I

N −
→ N0

bDPOC |Lift e

i.o? hvi@S:R

hI, N i −−−−−−−→ hI, N 0 i

I∈I

I

hI, N i −
→ hI, N 0 i

15

bDPOC |Lift-Up e

i.o? (x←v)@R:S

hI, N 00 i −−−−−−−−−−→ hI, N 000 i

o? :R(v)→S(x)

hI, N k N 00 i −−−−−−−−−→ hI, N 0 k N 000 i
i.o∗ (←X)@R:S

i.o∗ hXi@S:R

hI, N i −−−−−−−−→ hI, N 0 i
hI, N k

bDPOC |Synch e

hI, N 00 i −−−−−−−−−→ hI, N 000 i

o∗ :R(X)→S()
N 00 i −−−−−−−−→
η

hI, N i −
→ hI, N 0 i

hI, N 0

η 6=

k

√

η

hI, N k N 00 i −
→ hI, N 0 k N 00 i

bDPOC |Ext-Parallel e

√

√

hI, N i −
→ hI, N 0 i

hI, N 00 i −
→ hI, N 000 i
√

hI, N k N 00 i −
→ hI, N 0 k N 000 i
I0

hI, N i −
→

hI0 , N i

bDPOC |Synch-Up e

N 000 i

bDPOC |Ext-Par-End e

bDPOC |Change-Updates e

Figure 7: DPOC system semantics.
Definition 3.3 (DPOC traces). A (strong) trace of a DPOC system hI1 , N1 i is a sequence
(finite or infinite) of labels η1 , η2 , . . . with
√
ηi ∈ {τ, o? : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), , I, no-up, I}
η1

η2

such that there is a sequence of transitions hI1 , N1 i −→ hI2 , N2 i −→ . . . .
A weak trace of a DPOC system hI1 , N1 i is a sequence of labels η1 , η2 , . . . obtained by removing
all the labels corresponding to auxiliary communications, i.e., of the form o∗ : R1 (v) → R2 (x)
or o∗ : R1 (X) → R2 (), and the silent labels τ , from a trace of hI1 , N1 i.
DPOC traces do not allow send and receive actions. Indeed these actions represent
incomplete interactions, thus they are needed for compositionality reasons, but they do not
represent relevant behaviours of complete systems. Note also that these actions have no
correspondence at the DIOC level, where only whole interactions are allowed.
Remark 3.4. Contrarily to DIOCs, DPOCs in general can deadlock. For instance,

i: i.o : x from R0 , Γ R
is a deadlocked DPOC network: the process i: i.o : x from R0 is not terminated, and the
only enabled actions are changes of the set of updates (i.e., transitions with label I), which
are not actual system activities, but are taken by the environment. Notably, the DPOC
above cannot be obtained by projecting a DIOC. In fact, DPOCs generated from DIOCs are
guaranteed to be deadlock free.

16

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

4. Projection Function
We now introduce the projection function proj. Given a DIOC specification, proj returns a
network of DPOC programs that enact the behaviour defined by the originating DIOC.
We write the projection of a DIOC I as proj(I, Σ), where Σ is a global state. Informally,
the projection of a DIOC is a parallel composition of terms, one for each role of the DIOC.
The body of these roles is computed by the process-projection function π (defined below).
Given a DIOC and a role name R, the process-projection returns the process corresponding
to the local behaviour of role R. Since the roles executing the process-projections are
composed in parallel, the projection of a DIOC program results into the DPOC network of
the projected roles.
To give the formal definition of projection, we first define ki∈I Ni as the parallel
composition of networks Ni for i ∈ I.
Definition 4.1 (Projection). The projection of a DIOC process I with global state Σ is
the DPOC network defined by:
proj(I, Σ) =kS∈roles(I) (π(I, S), ΣS )S
The process-projection function that derives DPOC processes from DIOC processes is
defined as follows.
Definition 4.2 (Process-projection). Given an annotated DIOC process I and a role R
the projected DPOC process π(I, R) is defined as in Figure 8.
With a little abuse of notation, we write roles(I, I 0 ) for roles(I) ∪ roles(I 0 ). We assume
that variables xi are never used in the DIOC to be projected and we use them for auxiliary
synchronisations.
The projection is homomorphic for sequential and parallel composition, 1 and 0. The
projection of an assignment is the assignment on the role performing it and 1 on other roles.
The projection of an interaction is a send on the sender role, a receive on the receiver, and
1 on any other role. The projection of a scope is a scope on all its participants. On its
coordinator it also features a clause that records the roles of the involved participants. On
the roles not involved in the scope the projection is 1. Projections of conditional and while
loop are a bit more complex, since they need to coordinate a distributed computation. To
this end they exploit communications on auxiliary operations. In particular, cnd∗i coordinates
the branching of conditionals, carrying information on whether the “then” or the “else”
branch needs to be taken. Similarly, wb∗i coordinates the beginning of a while loop, carrying
information on whether to loop or to exit. Finally, we∗i coordinates the end of the body of
the while loop. This closing operation carries no relevant information and it is just used for
synchronisation purposes. In order to execute a conditional i: if b@R {I} else {I 0 }, the
coordinator R of the conditional locally evaluates the guard and tells the other roles which
branch to choose using auxiliary communications on cnd∗i . Finally, all the roles involved
in the conditional execute their code corresponding to the chosen branch. Execution of a
loop i: while b@R {I} is similar, with two differences. First, end of loop synchronisation
on operations we∗i is used to notify the coordinator that an iteration is terminated, and a
new one can start. Second, communication of whether to loop or to exit is more tricky than
communication on the branch to choose in a conditional. Indeed, there are two points in
the projected code where the coordinator R sends the decision: the first is inside the body
of the loop and it is used if the decision is to loop; the second is after the loop and it is

DYNAMIC CHOREOGRAPHIES

π(1, S) = 1
0

0

π(I; I , S) = π(I, S); π(I , S)

π(0, S) = 0
π(I|I 0 , S) = π(I, S)|π(I 0 , S)

π(i: x@R = e, R)

= i: x = e

π(i: x@R = e, S) and S 6= R

= 1

π(i: o : R1 (e) → R2 (x), R1 )

= i: i.o : e to R2

π(i: o : R1 (e) → R2 (x), R2 )

= i: i.o : x from R1

π(i: o : R1 (e) → R2 (x), S)
and S 6∈ {R1 , R2 }

= 1

π(i: if b@R {I} else {I 0 }, R)

=








i: if b






















17

Q

iT: i.cnd∗i : true to R0

! 


; 

R0 ∈roles(I,I 0 )\{R}






π(I,
R)
! 

Q





iF: i.cnd∗i : false to R0 ; 
else
R0 ∈roles(I,I 0 )\{R}






π(I 0 , R)

π(i: if b@R {I} else {I 0 }, S)
and S ∈ roles(I, I 0 ) \ {R}

= i?: i.cnd∗i : xi from R; i: if xi {π(I, S)} else {π(I 0 , S)}

π(i: if b@R {I} else {I 0 }, S)
and S 6∈ roles(I, I 0 ) ∪ {R}

= 1

π(i: while b@R {I}, R)

π(i: while b@R {I}, S)
and S ∈ roles(I) \ {R}

n


i: while b





!



Q

0
∗


iT: i.wbi : true to R ;



R0 ∈roles(I)\{R}

Q
=
iC: i.we∗i : from R0


 R0 ∈roles(I)\{R}








o
Q


iF: i.wb∗i : false to R0

 ;
0 ∈roles(I)\{R}
R

∗

 i?: i.wbi : xi from
 R;


 π(I, S);

=
∗
i: while xi iC: i.wei : ok to R;





i?: i.wb∗i : xi from R

π(i: while b@R {I}, S)
and S 6∈ roles(I) ∪ {R}

= 1

π(i: scope @R {I}, R)

= i: scope @R {π(I, R)} roles {roles(I)}

π(i: scope @R {I}, S)
and S ∈ roles(I) \ {R}

= i: scope @R {π(I, S)}

π(i: scope @R {I}, S)
and S 6∈ roles(I) ∪ {R}

= 1

Figure 8: process-projection function π.

π(I, R);

18

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

used if the decision is to exit. Also, there are two points where these communications are
received by the other roles: before their loop at the first iteration, at the end of the previous
iteration of the body of the loop in the others.
One has to keep attention since, by splitting an interaction into a send and a receive
primitive, primitives corresponding to different interactions, but on the same operation, may
interfere.
Example 4.3. We illustrate the issue of interferences using the two DPOC processes below,
identified by their respective roles, R1 (right) and R2 (left), assuming that operations are
not prefixed by indexes. We describe only R1 as R2 is its dual. At Line 1, R1 sends a
message to R2 on operation o. In parallel with the send, R1 had a scope (Lines 3–5) that
performed an update. The new code (Line 4) contains a send on operation o to role R2 .
Since the two sends and the two receives share the same operation o and run in parallel,
they can interfere with each other.
process R1
1. 1: o : e1 to R2
2. |
3. // update auxiliary code
4. 2: o : e2 to R2
5. // update auxiliary code

process R2
1. 1: o : x1 from R2
2. |
3. // update auxiliary code
4. 2: o : x2 from R2
5. // update auxiliary code

Note that, since updates come from outside and one cannot know in advance which
operations they use, this interference cannot be statically avoided.
For this reason, in § 3 we introduced indexes to prefix DPOC operations.
A similar problem may occur also for auxiliary communications. In particular, imagine
to have two parallel conditionals executed by the same role. We need to avoid that, e.g.,
the decision to take the “else” branch on the first conditional is wrongly taken by some
role as a decision concerning the second conditional. To avoid this problem, we prefix
auxiliary operations using the index i of the conditional. In this way, communications
involving distinct conditionals cannot interact. Note that communications concerning the
same conditional (or while loop) may share the same operation name and prefix. However,
since all auxiliary communications are from the coordinator of the construct to the other
roles involved in it, or vice versa, interferences are avoided.
We now describe how to generate indexes for statements in the projection. As a general
rule, all the DPOC constructs obtained by projecting a DIOC construct with index i have
index i. The only exceptions are the indexes of the auxiliary communications of the projection
of conditionals and while loops.
Provided i is the index of the conditional: i ) in the projection of the coordinator we
index the auxiliary communications for selecting the “then” branch with index iT , the
ones for selecting the “else” branch with index iF ; ii ) in the projection of the other roles
involved in the conditional we assign the index i? to the auxiliary receive communications.
To communicate the evaluation of the guard of a while loop we use the same indexing
scheme (iT , iF , and i? ) used in the projection of conditional. Moreover, all the auxiliary
communications for end of loop synchronisation are indexed with iC .

DYNAMIC CHOREOGRAPHIES

19

5. Running Example: Projection and Execution
In this section we use our running example (see Figure 2) to illustrate the projection and
execution of DIOC programs.
5.1. Projection. Given the code in Figure 2, we need to annotate it to be able to project it
(we remind that in § 4 we defined our projection function on well-annotated DIOCs). Since
we wrote one instruction per line in Figure 2, we annotate every instruction using its line
number as index. This results in a well-annotated DIOC.
From the annotated DIOC, the projection generates three DPOC processes for the
Seller, the Buyer, and the Bank, respectively reported in Figures 9, 11, and 10. To improve
readability, we omit some 1 processes. In the projection of the program, we also omit to
write the index that prefixes the operations since it is always equal to the numeric part of
the index of their correspondent construct. Finally, we write auxiliary communications in
grey.
5.2. Runtime Execution. We now focus on an excerpt of the code to exemplify how
updates are performed at runtime. We consider the code of the scope at Lines 6–9 of
Figure 2. In this execution scenario we assume to introduce in the set of available updates
the update presented in Figure 1, which enables the use of a fidelity card to provide a price
discount. Below we consider both the DIOC and the DPOC level, dropping some 1s to
improve readability.
Since we describe a runtime execution, we assume that the Buyer has just sent the
name of the product (s)he is interested in to the Seller (Line 5 of Figure 2). The annotated
DIOCs we execute is the following.
6: scope @Seller{
7: order price@Seller = getPrice(order);
3
8: offer : Seller(order price) → Buyer(prod price)
4 }
1
2

At runtime we apply Rule bDIOC |Up e that substitutes the scope with the new code. The
replacement is atomic. Below we assume that the instructions of the update are annotated
with indexes corresponding to their line number plus 30.
1
2
3
4
5
6
7
8
9

31: cardReq : Seller(null) → Buyer( );
32: card id@Buyer = getInput();
33: card : Buyer(card id) → Seller(buyer id);
34: if isValid(buyer id)@Seller{
35: order price@Seller = getPrice(order) ∗ 0.9
} else {
37: order price@Seller = getPrice(order)
};
39: offer : Seller(order price) → Buyer(prod price)

Let us now focus on the execution at DPOC level, where the application of updates
is not atomic. The scope is distributed between two participants. The first step of the

20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

3? : wb∗3 : x3 from Buyer;
3: while(x3 ){
5: priceReq : order from Buyer;
6: scope @Seller{
7: order price = getPrice(order);
8: offer : order price to Buyer
} roles { Seller, Buyer };
3C : we∗3 : ok to Buyer;
3? : wb∗3 : x3 from Buyer
};
15? : cnd∗15 : x15 from Buyer;
15: if (x15 ){
16: payReq : payDesc(order price) to Bank;
21? : cnd∗21 : x21 from Bank;
21: if (x21 ){
22: conf irm : from Bank }
}
Figure 9: Seller DPOC Process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

15? : cnd∗15

: x15 from Buyer;
15: if (x15 ){
16: payReq : desc from Seller;
17: scope @Bank{
18: pay : auth from Buyer
} roles {Buyer, Bank};
20: payment ok = makePayment(desc, auth);
21: if (payment ok){
{
21T : cnd∗21 : true to Seller
| 21T : cnd∗21 : true to Buyer
} ; {
22: conf irm : null to Seller
| 24: conf irm : null to Buyer
}
} else {
{
21F : cnd∗21 : false to Seller
| 21F : cnd∗21 : false to Buyer
};
26: abort : null to Buyer
}
}
Figure 10: Bank DPOC Process.

15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

1: price ok = false;
2: continue = true;
3: while(!price ok and continue){
3T : wb∗3 : true to Seller;
4: prod = getInput();
5: priceReq : prod to Seller;
6: scope @Seller{
7: offer : prod price from Seller
};
10: price ok = getInput();
11: if (!price ok){
12: continue = getInput()
};
3C : we∗3 : from Seller
};
3F : wb∗3 : false to Seller;
15: if (price ok){
{
15T : cnd∗15 : true to Seller
|15T : cnd∗15 : true to Bank
};
17: scope @Bank{
19: pay : payAuth(prod price) to Bank
};
21? : cnd∗21 : x21 from Bank;
21: if (x21 ){
24: conf irm : from Bank
} else {
26: abort : from Bank}
}
}

Figure 11: Buyer DPOC Process.

DYNAMIC CHOREOGRAPHIES

21

update protocol is performed by the Seller, since (s)he is the coordinator of the update.
The DPOC description of the Seller before the update is:
6: scope @Seller{
7: order price = getPrice(order);
8: offer : order price to Buyer
} roles {Seller, Buyer}
When the scope construct is enabled, the Seller non-deterministically selects whether
to update or not and, in the first case, which update to apply. Here, we assume that the
update using the code in Figure 1 is selected. Below we report on the left the reductum of
the projected code of the Seller after the application of Rule bDPOC |Lead-Up e. The Seller
sends to the Buyer the code — denoted as PB and reported below on the right — obtained
projecting the update on role Buyer.
1
2
3
4
5
6
7
8
9
10

6: sb∗6 : PB to Buyer;
31: cardReq : null to Buyer;
33: card : buyer id from Buyer;
34: if isValid(buyer id){
PB := 31: cardReq : null from Seller;
35: order price = getPrice(order) ∗ 0.9
32: card id = getInput();
} else {
33: card : card id to Seller;
37: order price = getPrice(order)
39: offer : prod price from Seller
};
39: offer : order price to Buyer;
6: se∗6 : from Buyer;

Above, at Line 1 the Seller requires the Buyer to update, sending to him the new
DPOC fragment to execute. Then, the Seller starts to execute its own updated DPOC.
At the end of the execution of the new DPOC code (Line 10) the Seller waits for the
notification of termination of the DPOC fragment executed by the Buyer.
Let us now consider the process-projection of the Buyer, reported below.
6: scope @Seller{
8: offer : order price from Seller
}
At runtime, the scope waits for the arrival of a message from the coordinator of the update.
In our case, since we assumed that the update is applied, the Buyer receives using Rule
bDPOC |Up e the DPOC fragment PB sent by the coordinator. In the reductum, PB replaces
the scope, followed by the notification of termination to the Seller.
31: cardReq : null from Seller;
32: card id = getInput();
33: card : card id to Seller;
39: offer : prod price from Seller
6: se∗6 : ok to Seller

22

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

Consider now what happens if no update is applied. At DIOC level the Seller applies
Rule bDIOC |NoUp e, which removes the scope and runs its body. At DPOC level, the update
is not atomic. The code of the Seller is the following one.
6: sb∗6 : no to Buyer;
2 7: order price = getPrice(order);
3 8: offer : order price to Buyer;
4 6: se∗6 : from Buyer;
1

Before executing the code inside the scope, the Seller notifies the Buyer that (s)he can
proceed with her execution (Line 1). Like in the case of update, the Seller also waits for
the notification of the end of execution from the Buyer (Line 4).
Finally, we report the DPOC code of the Buyer after the reception of the message that
no update is needed. Rule bDPOC |NoUp e removes the scope and adds the notification of
termination (Line 2 below) to the coordinator at the end.
1
2

7: offer : prod price from Seller;
6: se∗6 : ok to Seller;
6. Connected DIOCs

We now give a precise definition of the notion of connectedness that we mentioned in § 2.2
and § 3.2. In both DIOC and DPOC semantics we checked such a property of updates with
predicate connected, respectively in Rule bDIOC |Up e (Figure 3) and Rule bDPOC |Up-Lead e
(Figure 6).
To give the intuition of why we need to restrict to connected updates, consider the
scenario below of a DIOC (left side) and its projection (right side).
op1 : A(e1 ) → B(x);
op2 : C(e2 ) → D(y)

projection

======⇒

process A
op1 : e1 to B

process B
op1 : x from A

process C
op2 : e2 to D

process D
op2 : y from C

DIOCs can express interactions that, if projected as described in § 4, can behave differently
with respect to the originating DIOC. Indeed, in our example we have a DIOC that composes
in sequence two interactions: an interaction between A and B on operation op1 followed by
an interaction between C and D on operation op2 . The projection of the DIOC produces
four processes (identified by their role): A and C send a message to B and D, respectively.
Dually, B and D receive a message form A and C, respectively. In the example, at the level
of processes we lose the global order among the interactions: each projected process runs its
code locally and it is not aware of the global sequence of interactions. Indeed, both sends
and both receives are enabled at the same time. Hence, the semantics of DPOC lets the two
interactions interleave in any order. It can happen that the interaction between C and D
occurs before the one between A and B, violating the order of interactions prescribed by
the originating DIOC.
Restricting to connected DIOCs avoids this kind of behaviours. We formalise connectedness as an efficient (see Theorem 6.3) syntactic check. We highlight that our definition of
connectedness does not hamper programmability and it naturally holds in most real-world

DYNAMIC CHOREOGRAPHIES

23

scenarios (the interested reader can find in the website of the AIOCJ project [1] several such
scenarios).
Remark 6.1. There exists a trade-off between efficiency and ease of programming with
respect to the guarantee that all the roles are aware of the evolution of the global computation.
This is a common element of choreographic approaches, which has been handled in different
ways, e.g., i ) by restricting the set of well-formed choreographies to only those on which
the projection preserves the order of actions [10]; ii ) by mimicking the non-deterministic
behaviour of process-level networks at choreography level [13]; or iii ) by enforcing the order
of actions with additional auxiliary messages between roles [31].
Our choice of preserving the order of interactions defined at DIOC level follows the same
philosophy of [10], whilst for scopes, conditionals, and while loops we enforce connectedness
with auxiliary messages as done in [31]. We remind that we introduced auxiliary messages
for coordination both in the semantics of scopes at DPOC level (§ 3.2) and in the projection
(§ 4). We choose to add such auxiliary messages to avoid to impose strong constraints on the
form of scopes, conditionals, and while loops, which in the end would pose strong limitations
to the programmers of DIOCs. On the other hand, for sequential composition we choose to
restrict the set of allowed DIOCs by requiring connectedness, which ensures that the order
of interactions defined at DIOC level is preserved by projection.
As discussed above, the execution of conditionals and while loops rely on auxiliary
communications to coordinate the different roles. Some of these communications may be
redundant. For instance, in Figure 9, Line 8, the Seller notifies to the Buyer that (s)he
has completed her part of the while loop. However, since her last contribution to the while
loop is the auxiliary communication for end of scope synchronisation, the Buyer already
has this information. Hence, Line 8 in Figure 9, where the notification is sent, and Line 14
in Figure 11, where the notification is received, can be safely dropped. Removing redundant
auxiliary communications can be automatised using a suitable static analysis. We leave this
topic for future work.
To formalise connectedness we introduce, in Figure 12, the auxiliary functions transI and
transF that, given a DIOC process, compute sets of pairs representing senders and receivers
of possible initial and final interactions in its execution. We represent one such pair as
R → S. Actions located at R are represented as R → R. For instance, given an interaction
i : o : R(e) → S(x) both its transI and transF are {R → S}. For conditional, transI(i :
if b@R {I} else {I 0 }) = {R → R} since the first action executed is the evaluation of the
guard by role R. The set transF(i: if b@R {I} else {I 0 }) is normally transF(I) ∪ transF(I 0 ),
since the execution terminates with an action from one of the branches. If instead the
branches are both empty then transF is {R → R}, representing guard evaluation.
Finally, we give the formal definition of connectedness.
Definition 6.2 (Connectedness). A DIOC process I is connected if each subterm I 0 ; I 00 of
I satisfies
∀ R1 → R2 ∈ transF(I 0 ), ∀ S1 → S2 ∈ transI(I 00 ) . {R1 , R2 } ∩ {S1 , S2 } =
6 ∅
Connectedness can be checked efficiently.
Theorem 6.3 (Connectedness-check complexity).
The connectedness of a DIOC process I can be checked in time O(n2 log(n)), where n is the
number of nodes in the abstract syntax tree of I.

24

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

transI(i: o : R(e) → S(x))

= transF(i: o : R(e) → S(x)) = {R → S}

transI(i: x@R = e)

= transF(i: x@R = e) = {R → R}

transI(1)

= transI(0) = transF(1) = transF(0) = ∅

transI(I|I 0 )

= transI(I) ∪ transI(I 0 )

transF(I|I 0 )

= transF(I) ∪ transF(I 0 )
(
transI(I 0 ) if transI(I) = ∅
=
transI(I) otherwise
(
transF(I) if transF(I 0 ) = ∅
=
transF(I 0 ) otherwise

transI(I; I 0 )
transF(I; I 0 )
transI(i: if b@R {I} else {I 0 })

= transI(i: while b@R {I}) = {R → R}
(
{R → R}
if transF(I) ∪ transF(I 0 ) = ∅
transF(i: if b@R {I} else {I 0 }) =
transF(I) ∪ transF(I 0 ) otherwise

if transF(I) = ∅
{R → R}
S
0
transF(i: while b@R {I})
=
{R → R } otherwise

R0 ∈roles(I)r{R}
transI(i: scope @R {I})
= {R → R}

if roles(I) ⊆ {R}
{R → R}
S
0
transF(i: scope @R {I})
=
{R → R} otherwise

R0 ∈roles(I)r{R}
Figure 12: Auxiliary functions transI and transF.
The proof of the theorem is reported in Appendix A.
We remind that we allow only connected updates. Indeed, replacing a scope with a
connected update always results in a deadlock- and race-free DIOC. Thus, one just needs to
statically check connectedness of the starting program and of the updates, and there is no
need to perform expensive runtime checks on the whole application after updates have been
performed.
7. Correctness
In the previous sections we have presented DIOCs, DPOCs, and described how to derive
a DPOC from a given DIOC. This section presents the main technical result of the paper,
namely the correctness of the projection. Moreover, as a consequence of the correctness, in
Section 7.2 we prove that properties like deadlock freedom, termination, and race freedom
are preserved by the projection.
Correctness here means that a connected DIOC and its projected DPOC are weak
system bisimilar. Weak system bisimilarity is formally defined as follows.
Definition 7.1 (Weak System Bisimilarity). A weak system bisimulation is a relation R
between DIOC systems and DPOC systems such that if (hΣ, I, Ii , hI0 , N i) ∈ R then:

DYNAMIC CHOREOGRAPHIES

µ

η1

η

25

µ

k
−
→ hI000 , N 000 i with
• if hΣ, I, Ii −
→ hΣ00 , I00 , I 00 i then hI0 , N i −→, . . . , −→
∗
∗
∀ i ∈ [1 . . . k], ηi ∈ {o : R1 (v) → R2 (x), o : R1 (X) → R2 (), τ } and
(hΣ00 , I00 , I 00 i , hI000 , N 000 i) ∈ R;
√
η
• if hI0 , N i −
→ hI000 , N 000 i with η ∈ {o? : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), , I,
no-up, I000 , τ } then one of the following two conditions holds:
η
– hΣ, I, Ii −
→ hΣ00 , I0 , I 00 i and (hΣ00 , I00 , I 00 i , hI000 , N 000 i) ∈ R or
– η ∈ {o∗ : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), τ } and (hΣ, I, Ii , hI000 , N 000 )i ∈ R
A DIOC system hΣ, I, Ii and a DPOC system hI0 , N i are weak system bisimilar iff there
exists a weak system bisimulation R such that (hΣ, I, Ii , hI0 , N i) ∈ R.

In the proof, we provide a relation R which relates each well-annotated connected DIOC
system with its projection and show that it is a weak system bisimulation. Such a relation
is not trivial since events that are atomic in the DIOC, e.g., the evaluation of the guard of a
conditional, including the removal of the discarded branch, are not atomic at DPOC level.
In the case of conditional, the DIOC transition is mimicked by a conditional performed
by the role evaluating the guard, a set of auxiliary communications sending the value of
the guard to the other roles, and local conditionals based on the received value. These
mismatches are taken care by function upd (Definition 7.18). This function needs also to
remove the auxiliary communications used to synchronise the termination of scopes, which
have no counterpart after the DIOC scope has been consumed. However, we have to record
the impact of the mentioned auxiliary communications on the possible executions. Thus we
define an event structure for DIOC (Definition 7.10) and one for DPOC (Definition 7.11)
and we show that the two are related (Lemma 7.15).
Thanks to the existence of a bisimulation relating each well-annotated connected DIOC
system with its projection we can prove that the projection is correct. Formally:
Theorem 7.2 (Correctness). For each initial, connected DIOC process I, each state Σ,
each set of updates I, the DIOC system hΣ, I, Ii and the DPOC system hI, proj(I, Σ)i are
weak system bisimilar.
As a corollary of the result above, a DIOC system and its projection are also trace
equivalent. Trace equivalence is defined as follows.
Definition 7.3 (Trace equivalence). A DIOC system hΣ, I, Ii and a DPOC system hI, N i
are (weak) trace equivalent iff their sets of (weak) traces coincide.
The following lemma shows that, indeed, weak system bisimilarity implies weak trace
equivalence.
Lemma 7.4. Let hΣ, I, Ii be a DIOC system and hI0 , N i a DPOC system.
If hΣ, I, Ii ∼ hI0 , N i then the DIOC system hΣ, I, Ii and the DPOC system hI0 , N i are weak
trace equivalent.
Proof. The proof is by coinduction. Take a DIOC trace µ1 , µ2 , . . . of the DIOC system.
From bisimilarity, the DPOC system has a sequence of transitions with labels η1 , . . . , ηk , µ1
where η1 , . . . , ηk are weak transitions. Hence, the first label in the weak trace is µ1 . After
the transition with label µ1 , the DIOC system and the DPOC system are again bisimilar.
By coinductive hypothesis, the DPOC system has a weak trace µ2 , . . .. By composition the
DPOC system has a trace µ1 , µ2 , . . . as desired. The opposite direction is similar.

26

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

Hence the following corollary holds.
Corollary 7.5 (Trace Equivalence). For each initial, connected DIOC process I, each state
Σ, each set of updates I, the DIOC system hΣ, I, Ii and the DPOC system hI, proj(I, Σ)i are
weak trace equivalent.
Proof. It follows from Theorem 7.2 and Lemma 7.4.
The following section presents the details of the proof of Theorem 7.2. The reader not
interested in such details can safely skip § 7.1 and go to § 7.2.
7.1. Detailed Proof of Correctness. In our proof strategy we rely on the distinctness of
indexes of DIOC constructs that, unfortunately, is not preserved by transitions due to while
unfolding.
Example 7.6. Consider the DIOC i : while b@R {j : x@R = e}. If the condition b
evaluates to true, in one step the application of Rule bDPOC |While-unfold e produces the
DIOC I below
j: x@R = e; i: while b@R {j: x@R = e}
where the index j occurs twice.
To solve this problem, instead of using indexes, we rely on global indexes built on top of
indexes. Global indexes can be used both at the DIOC level and at the DPOC level and
their distinctness is preserved by transitions.
Definition 7.7 (Global index). Given an annotated DIOC process I, or an annotated
DPOC network N , for each annotated construct with index ι we define its global index ξ as
follows:
• if the construct is not in the body of a while loop then ξ = ι;
• if the innermost while construct that contains the considered construct has global index
ξ 0 then the considered construct has global index ξ = ξ 0 : ι.
Example 7.8. Consider the DIOC I in Example 7.6. The first assignment with index j
also has global index j, while the second assignment with index j has global index i: j, since
this last assignment is inside a while loop with global index i.
Lemma 7.9 (Distinctness of Global Indexes). Given a well-annotated DIOC I, a global
η1
ηn
state Σ, and a set of updates I, if hΣ, I, Ii −→ . . . −→ hΣ0 , I0 , I 0 i then all global indexes in I 0
are distinct.
Proof. The proof is by induction on the number n of transitions. Details are in Appendix B.
Using global indexes we can now define event structures corresponding to the execution
of DIOCs and DPOCs. We start by defining DIOC events. Some events correspond to
transitions of the DIOC, and we say that they are enabled when the corresponding transition
is enabled, executed when the corresponding transition is executed.
Definition 7.10 (DIOC events). We use ε to range over events, and we write [ε]R to
highlight that event ε is performed by role R. An annotated DIOC I contains the following
events:

DYNAMIC CHOREOGRAPHIES

27

Communication events: a sending event ξ : o@R2 in role R1 and a receiving event
ξ : o@R1 in role R2 for each interaction i: o : R1 (e) → R2 (x) with global index ξ; we also
denote the sending event as fξ or [fξ ]R1 and the receiving event as tξ or [tξ ]R2 . Sending and
receiving events correspond to the transition executing the interaction.
Assignment events: an assignment event εξ in role R for each assignment i: x@R = e
with global index ξ; the event corresponds to the transition executing the assignment.
Scope events: a scope initialisation event ↑ξ and a scope termination event ↓ξ for
each scope i: scope @R {I} with global index ξ. Both these events belong to all the roles
in roles(I). The scope initialisation event corresponds to the transition performing or not
performing an update on the given scope. The scope termination event is just an auxiliary
event (related to the auxiliary interactions implementing the scope termination).
If events: a guard if-event εξ in role R for each construct i: if b@R {I} else {I 0 } with
global index ξ; the guard-if event corresponds to the transition evaluating the guard of the
condition.
While events: a guard while-event εξ in role R for each construct i: while b@R {I}
with global index ξ; the guard-while event corresponds to the transition evaluating the guard
of the while loop.
Function events(I) denotes the set of events of the annotated DIOC I. A sending and a
receiving event with the same global index ξ are called matching events. We denote with ε
an event matching event ε. A communication event is either a sending event or a receiving
event. A communication event is unmatched if there is no event matching it.
As a corollary of Lemma 7.9 events have distinct names. Note also that, for each while
loop, there are events corresponding to the execution of just one iteration of the loop. If
unfolding is performed, new events are created.
Similarly to what we have done for DIOC, we can define events for DPOC as follows.
Definition 7.11 (DPOC events). An annotated DPOC network N contains the following
events:
Communication events: a sending event ξ : o? @R2 in role R1 for each send ι : i.o? :
e to R2 with global index ξ in role R1 ; and a receiving event ξ : o? @R1 in role R2 for
each receive ι: i.o? : x from R1 with global index ξ in role R2 ; we also denote the sending
event as fξ or [fξ ]R1 ; and the receiving event as tξ or [tξ ]R2 . Sending and receiving events
correspond to the transitions executing the corresponding communication.
Assignment events: an assignment event εξ in role R for each assignment i: x = e with
global index ξ; the event corresponds to the transition executing the assignment.
Scope events: a scope initialisation event ↑ξ and a scope termination event ↓ξ for each
i: scope @R {P } roles {S} or i: scope @R {P } with global index ξ. Scope events with
the same global index coincide, and thus the same event may belong to different roles;
the scope initialisation event corresponds to the transition performing or not performing
an update on the given scope for the role leading the update. The scope termination
event is just an auxiliary event (related to the auxiliary interactions implementing the
scope termination).
If events: a guard if-event εξ in role R for each construct i: if b {P } else {P 0 } with global
index ξ; the guard-if event corresponds to the transition evaluating the guard of the
condition.

28

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

While events: a guard while-event εξ in role R for each construct i: while b {P } with
global index ξ; the guard-while event corresponds to the transition evaluating the guard
of the while loop.
Let events(N ) denote the set of events of the network N . A sending and a receiving event
with either the same global index ξ or with global indexes differing only for replacing index
i? with iT or iF are called matching events. We denote with ε an event matching event ε.
With a slight abuse of notation, we write events(P ) to denote events originated by
constructs in process P , assuming the network N to be understood. We use the same syntax
for events of DIOCs and of DPOCs. Indeed, the two kinds of events are strongly related (cf.
Lemma 7.15).
We define below a causality relation ≤DIOC among DIOC events based on the constraints
given by the semantics on the execution of the corresponding transitions.
Definition 7.12 (DIOC causality relation). Let us consider an annotated DIOC I. A
causality relation ≤DIOC ⊆ events(I) × events(I) is the minimum reflexive and transitive
relation satisfying:
Sequentiality: let I 0 ; I 00 be a subterm of DIOC I. If ε0 is an event in I 0 and ε00 is an
event in I 00 , then ε0 ≤DIOC ε00 .
Scope: let i: scope @R {I 0 } be a subterm of DIOC I. If ε0 is an event in I 0 then
↑ξ ≤DIOC ε0 ≤DIOC ↓ξ .
Synchronisation: for each interaction the sending event precedes the receiving event.
If: let i: if b@R {I 00 } else {I 00 } be a subterm of DIOC I, let εξ be the guard if-event
in role R, then for every event ε0 in I 0 and for every event ε00 in I 00 we have εξ ≤DIOC ε0
and εξ ≤DIOC ε00 .
While: let i: while b@R {I 0 } be a subterm of DIOC I, let εξ be the guard while-event
in role R, then for every event ε0 in I 0 we have εξ ≤DIOC ε0 .
As expected, the relation ≤DIOC is a partial order.
Lemma 7.13. Let us consider an annotated DIOC I. The relation ≤DIOC among events
of I is a partial order.
Proof. A partial order is a relation which is reflexive, transitive, and antisymmetric. Reflexivity and transitivity follow by definition. We show antisymmetry by showing that ≤DIOC
does not contain any cycle. The proof is by structural induction on the DIOC I. The base
cases are interaction, assignment, 1, and 0, which are all trivial. In the case of sequence,
I 0 ; I 00 , by inductive hypothesis there are no cycles among the events of I 0 nor among events
of I 00 . Since all events of I 0 precede all events of I 00 , there are no cycles among the events
of I 0 ; I 00 . In the case of parallel composition, I 0 |I 00 , there is no relation between events in
I 0 and in I 00 , hence the thesis follows. In the case of conditional i: if b@R {I 0 } else {I 00 }
there are no relations between events in I 0 and in I 00 and all the events follow the guard-if
event. Hence the thesis follows. The cases of while and scope are similar.
We can now define a causality relation ≤DP OC among DP OC events.
Definition 7.14 (DPOC causality relation). Let us consider an annotated DPOC network
N . A causality relation ≤DP OC ⊆ events(N ) × events(N ) is the minimum reflexive and
transitive relation satisfying:
Sequentiality: Let P 0 ; P 00 be a subterm of DPOC network N . If ε0 is an event in P 0
and ε00 is an event in P 00 then ε0 ≤DP OC ε00 .

DYNAMIC CHOREOGRAPHIES

29

Scope: Let i: scope @R {P } roles {S} or i: scope @R {P } be a subterm of DPOC
N with global index ξ. If ε0 is an event in P then ↑ξ ≤DP OC ε0 ≤DP OC ↓ξ .
Synchronisation: For each pair of events ε and ε0 , ε ≤ ε0 implies ε ≤DP OC ε0 .
If: Let i: if b {P } else {P 0 } be a subterm of DPOC network N with global index ξ, let
εξ be the guard if-event, then for every event ε in P and for every event ε0 in P 0 we have
εξ ≤DP OC ε and εξ ≤DP OC ε0 .
While: Let i: while b {P } be a subterm of DPOC network N with global index ξ, let
εξ be the guard while-event, then for every event ε in P we have εξ ≤DP OC ε.
On DP OC networks obtained as projections of well-annotated DIOCs the relation
≤DP OC is a partial order, as expected. However, since this result is not needed in the
remainder of the paper, we do not present its proof.
There is a relation between DIOC events and causality relation and their counterparts
at the DP OC level. Indeed, the events and causality relation are preserved by projection.
Lemma 7.15. Given a well-annotated connected DIOC process I and for each state Σ the
DPOC network proj(I, Σ) is such that:
(1) events(I) ⊆ events(proj(I, Σ));
(2) ∀ ε1 , ε2 ∈ events(I).ε1 ≤DIOC ε2 ⇒ ε1 ≤DP OC ε2 ∨ ε1 ≤DP OC ε2
Proof. The events of a DPOC obtained by projecting a DIOC I are included in the events
of the DIOC I by definition of projection. The preservation of the causality relation can be
proven by a case analysis on the condition used to derive the dependency (i.e., sequentiality,
scope, synchronisation, if and while). Details are in Appendix B.
To complete the definition of our event structure we now define a notion of conflict between
(DIOC and DPOC) events, relating events which are in different branches of the same
conditional.
Definition 7.16 (Conflicting events). Given a DIOC process I, two events ε, ε0 ∈ events(I)
are conflicting if they belong to different branches of the same conditional, i.e., there exists
a subprocess i: if b@R {I 0 } else {I 00 } of I such that ε ∈ events(I 0 ) ∧ ε0 ∈ events(I 00 ) or
ε0 ∈ events(I 0 ) ∧ ε ∈ events(I 00 ).
Similarly, given a DPOC network N , we say that two events ε, ε0 ∈ events(N ) are
conflicting if they belong to different branches of the same conditional, i.e., there exists
a subprocess i : if b {P } else {P 0 } of N such that ε ∈ events(P ) ∧ ε0 ∈ events(P 0 ) or
ε0 ∈ events(P ) ∧ ε ∈ events(P 0 ).
Similarly to what we did for DIOCs, we define below well-annotated DPOCs. Wellannotated DPOCs include all DPOCs obtained by projecting well-annotated DIOCs. As
stated in the definition below, and proved in Lemma 7.20, well-annotated DPOCs enjoy
various properties useful for our proofs.
Definition 7.17 (Well-annotated DPOC). An annotated DPOC network N is well annotated for its causality relation ≤DP OC if the following conditions hold:
C1: for each global index ξ there are at most two communication events on programmerspecified operations with global index ξ and, in this case, they are matching events;
C2: only events which are minimal according to ≤DP OC may correspond to enabled transitions;

30

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

C3: for each pair of non-conflicting sending events [fξ ]R1 and [fξ0 ]R1 on the same operation i.o? with the same target R2 such that ξ 6= ξ 0 we have [fξ ]R1 ≤DP OC [fξ0 ]R1 or
[fξ0 ]R1 ≤DP OC [fξ ]R1 ;
C4: for each pair of non-conflicting receiving events [tξ ]R2 and [tξ0 ]R2 on the same operation
i.o? with the same sender R1 such that ξ 6= ξ 0 we have [tξ ]R2 ≤ [tξ0 ]R2 or [tξ0 ]R2 ≤ [tξ ]R2 ;
C5: if ε is an event inside a scope with global index ξ then its matching events ε (if they
exist) are inside a scope with the same global index.
C6: if two events have the same index but different global indexes then one of them, let us
call it ε1 , is inside the body of a while loop with global index ξ1 and the other, ε2 , is not.
Furthermore, ε2 ≤DP OC εξ1 where εξ1 is the guarding while-event of the while loop with
global index ξ1 .
Since scope update, conditional, and iteration at the DIOC level happen in one step, while
they correspond to many steps of the projected DPOC, we introduce a function, denoted
upd, that bridges this gap. More precisely, function upd is obtained as the composition of
two functions, a function compl that completes the execution of DIOC actions which have
already started, and a function clean that eliminates all the auxiliary closing communications
of scopes (scope execution introduces in the DPOC auxiliary communications which have
no correspondence in the DIOC).
Definition 7.18 (upd function). Let N be an annotated DPOC (we drop indexes if
not relevant). The upd function is defined as the composition of a function compl and a
function clean. Thus, upd(N ) = clean(compl(N )). Network compl(N ) is obtained from N
by repeating the following operations while possible.
(1) Performing the reception of the positive evaluation of the guard of a while loop, by
replacing for every i.wb∗i : true to R0 enabled, all the terms
i.wb∗i : xi from R; while xi {P ; i.we∗i : ok to R; i.wb∗i : xi from R}
not inside another while construct, with
P ; i.we∗i : ok to R; i.wb∗i : xi from R; while xi {P ; i.we∗i : ok to R; i.wb∗i : xi from R}
and replace i.wb∗i : true to R0 with 1.
(2) Performing the reception of the negative evaluation of the guard of a while loop by
replacing, for every i.wb∗i : false to R0 enabled, all the terms
i.wb∗i : xi from R; while xi {P ; i.we∗i : ok to R; i.wb∗i : xi from R}
not inside another while construct, with 1, and replace i.wb∗i : false to R0 with 1.
(3) Performing the unfolding of a while loop by replacing every
while xi {P ; i.we∗i : ok to R; i.wb∗i : xi from R}
enabled not inside another while construct, such that xi evaluates to true in the local
state, with
P ; i.we∗i : ok to R; i.wb∗i : xi from R; while xi {P ; i.we∗i : ok to R; i.we∗i : xi from R}
(4) Performing the termination of while loop by replacing every
while xi {P ; i.we∗i : ok to R; i.wb∗i : xi from R}
enabled not inside another while construct, such that xi evaluates to false in the local
state, with 1.

DYNAMIC CHOREOGRAPHIES

31

(5) Performing the reception of the positive evaluation of the guard of a conditional by
replacing, for every i.cnd∗i : true to R0 enabled, all the terms
i.cnd∗i : xi from R; if xi {P 0 } else {P 00 }
not inside a while construct with P 0 , and replace i.cnd∗i : true to R0 with 1.
(6) Performing the reception of the negative evaluation of the guard of a conditional by
replacing, for every i.cnd∗i : false to R0 enabled, all the terms
i.cnd∗i : xi from R; if xi {P 0 } else {P 00 }
not inside a while construct, with P 00 , and replace i.cnd∗i : false to R0 with 1.
(7) Performing the selection of the “then” branch by replacing every
if xi {P 0 } else {P 00 }
enabled, such that xi evaluates to true in the local state, with P 0 .
(8) Performing the selection of the “else” branch by replacing every
if xi {P 0 } else {P 00 }
enabled, such that xi evaluates to false in the local state, with P 00 .
(9) Performing the communication of the updated code by replacing, for every
i.sb∗i : P to S enabled, all the terms
i: scope @R {P 0 }
in role S not inside a while construct with P , and replace i.sb∗i : P to S with 1.
(10) Performing the communication that no update is needed by replacing, for each
i.sb∗i : no to S enabled, all the terms
i: scope @R {P 0 }
in role S not inside a while construct with P 0 , and replace i.sb∗i : P to S with 1.
Network clean(N ) is obtained from N by repeating the following operations while possible:
• Removing the auxiliary communications for end of scope and end of while loop synchronisation by replacing each
i.se∗i : ok to R
i.se∗i : from R

iC : i.we∗i : ok to R
iC : i.we∗i : from R

not inside a while construct with 1.
Furthermore clean may apply 0 or more times the following operation:
• replace a subterm 1; P by P or a subterm 1 | P by P .
Note that function compl does not reduce terms inside a while construct. Assume, for
instance, to have an auxiliary send targeting a receive inside the body of a while loop.
These two communications should not interact since they have different global indexes. This
explains why we exclude terms inside the body of while loops.
We proceed now to prove some of the proprieties of DIOC and DPOC. The first result
states that in a well-annotated DPOC only transitions corresponding to events minimal with
respect to the causality relation ≤DP OC may be enabled.
Lemma 7.19. If N is a DPOC, ≤DP OC its causality relation and ε is an event corresponding
to a transition enabled in N then ε is minimal with respect to ≤DP OC .

32

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

Proof. The proof is by contradiction. Suppose ε is enabled but not minimal, i.e., there exists
ε0 such that ε0 ≤DP OC ε. If there is more than one such ε0 consider the one such that the
length of the derivation of ε0 ≤DP OC ε is minimal. This derivation should have length one,
and following Definition 7.14 it may result from one of the following cases:
• Sequentiality: ε0 ≤DP OC ε means that ε0 ∈ events(P 0 ), ε ∈ events(P 00 ), and P 0 ; P 00 is a
subterm of N . Because of the semantics of sequential composition ε cannot be enabled.
• Scope: let i: scope @R {P } roles {S} or i: scope @R {P } be a subprocess of N with
global index ξ. We have the following cases:
– ε0 =↑ξ and ε ∈ events(P ), and this implies that ε cannot be enabled since if ε0 is enabled
then the Rule bDPOC |Up e or Rule bDPOC |NoUp e for starting the execution of the scope
have not been applied yet;
– ε0 =↑ξ and ε =↓ξ , or ε0 ∈ events(P ) and ε =↓ξ : this is trivial, since ↓ξ is an auxiliary
event and no transition corresponds to it;
• If: ε0 ≤DP OC ε means that ε0 is the evaluation of the guard of a subterm
i : if xi {P 0 } else {P 00 } and ε ∈ events(P 0 ) ∪ events(P 00 ). Event ε cannot be enabled
because of the semantics of conditionals.
• While: ε0 ≤DP OC ε means that ε0 is the evaluation of the guard of a subterm
i: while xi {P } and ε ∈ events(P ). Event ε cannot be enabled because of the semantics
of the while loop.
We now prove that all the DPOCs obtained as projection of well-annotated connected DIOCs
are well-annotated.
Lemma 7.20. Let I be a well-annotated connected DIOC process and Σ a state. Then the
projection N = proj(I, Σ) is a well-annotated DPOC network with respect to ≤DP OC .
Proof. We have to prove that proj(I, Σ) satisfies the conditions of Definition 7.17. We have
a case for each condition. Details in Appendix B.
The next lemma shows that for every starting set of updates I the DPOC N and upd(N )
have the same set of weak traces.
Lemma 7.21. Let N be a DPOC. The following properties hold:

√
η
(1) if hI, upd(N )i −
→ hI0 , N 0 i with η ∈ {o? : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), I0 , , I,
η1
ηk η
no-up, τ } then there exists N 00 such that hI, N i −→ . . . −→
−
→ hI0 , N 00 i where ηi ∈ {o∗ :
∗
R1 (v) → R2 (x), o : R1 (X) → R2 (), τ } for each i ∈ {1, . . . , k} and upd(N 00 ) = upd(N 0 ).
√
η
(2) if hI, N i −
→ hI0 , N 0 i for η ∈ {o? : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), I0 , , I, no-up, τ },
then one of the following holds:
(a) upd(N ) = upd(N 0 ) and η ∈ {o∗ : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), τ }, or
η
(b) hI, upd(N )i −
→ hI0 , N 00 i such that upd(N 0 ) = upd(N 00 ).

DYNAMIC CHOREOGRAPHIES

33

Proof.
(1) Applying the upd function corresponds to perform weak transitions, namely transitions
with labels in {o∗ : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), τ }. Some of such transitions
may not be enabled yet. Hence, N may perform the subset of the weak transitions
above which are or become enabled, reducing to some N 000 . Then, η is enabled also in
η
N 000 and we have hI, N 000 i −
→ hI0 , N 00 i. At this point we have that N 00 and N 0 may differ
only for the weak transitions that were never enabled, which can be executed by upd.
(2) There are two cases. In the first case the transition with label η is one of the transitions
executed by function upd. In this case the condition 2a holds. In the second case, the
transition with label η is not one of the transitions executed by function upd. In this
case the transition with label η is still enabled in upd(N ) and can be executed. This
leads to a network that differs from N 0 only because of transitions executed by the upd
function and case 2b holds.
√
We now prove a property of transitions with label .
√
Lemma 7.22. For each DIOC system hΣ, I, Ii that reduces with a transition labelled
then, for√each role R ∈ roles(I), the DPOC role (π(I, R), ΣR )R can reduce with a transition
labelled
and vice versa.
√
Proof. Note that a DIOC can perform a transition with label only if it is a term obtained
using sequential and/or parallel composition starting from 1 constructs. The projection has
the same shape, hence it can perform the desired transition. The other direction is similar.
We can now prove our main theorem (Theorem 7.2, restated below) for which, given a
connected well-annotated DIOC process I and a state Σ, the DPOC network obtained as
its projection has the same behaviours of I.
Theorem 7.2 (Correctness). For each initial, connected DIOC process I, each state Σ,
each set of updates I, the DIOC system hΣ, I, Ii and the DPOC system hI, proj(I, Σ)i are
weak system bisimilar.
Proof. We prove that the relation R below is a weak system bisimulation.





upd(N ) = proj(I, Σ),
events(I) ⊆ events(compl(N )),
R=
(hΣ, I, Ii , hI, N i)
∀
ε1 , ε2 ∈ events(I) .



ε1 ≤DIOC ε2 ⇒ ε1 ≤DP OC ε2 ∨ ε1 ≤DP OC ε2









where I is obtained from a well-annotated connected DIOC via 0 or more transitions
and upd(N ) is a well-annotated DPOC.
To ensure that proving that the relation above is a weak system bisimulation implies
our thesis, let us show that the pair (hΣ, I, Ii , hI, proj(I, Σ)i) from the theorem statement
belongs to R. Note that here I is well-annotated and connected, and for each such
I we have upd(proj(I, Σ)) = proj(I, Σ). From Lemma 7.20 proj(I, Σ) is well-annotated,
thus upd(proj(I, Σ)) is well-annotated. Observe that compl is the identity on proj(I, Σ),
thus from Lemma 7.15 we have that the conditions events(I) ⊆ events(compl(N )) and
∀ε1 , ε2 ∈ events(I) . ε1 ≤DIOC ε2 ⇒ ε1 ≤DP OC ε2 ∨ ε1 ≤DP OC ε2 are satisfied.

34

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

We now prove that R is a weak system bisimulation. To prove it, we show below that
it is enough to consider only the case in which N (and not upd(N )) is equal to proj(I, Σ).
Furthermore, in this case the transition of hΣ, I, Ii is matched by the first transition of
hI, proj(I, Σ)i.
Formally, for each (hΣ, I, Ii , hI, N i) where N = proj(I, Σ) we have to prove the following
simplified bisimulation clauses.
µ

µ

• if hΣ, I, Ii −
→ hΣ00 , I00 , I 00 i then hI, N i −
→ hI00 , N 000 i with (hΣ00 , I00 , I 00 i , hI00 , N 000 i) ∈ R;
√
η
• if hI, N i −
→ hI00 , N 000 i with η ∈ {o : R1 (v) → R2 (x); ; I; no-up; I00 ; τ } then
η
hΣ, I, Ii −
→ hΣ00 , I00 , I 00 i and (hΣ00 , I00 , I 00 i , hI00 , N 000 i) ∈ R.
µ

In fact, consider a general network Ng with upd(Ng ) = proj(I, Σ). If hΣ, I, Ii −
→ hΣ00 , I00 , I 00 i,
µ
then by hypothesis hI, upd(Ng )i −
→ hI00 , N 000 i. From Lemma 7.21 case 1 there exists N 00 such
η1
ηk µ
that hI, Ng i −→ . . . −→−
→ hI00 , N 00 i where ηi ∈ {o∗ : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), τ }
for each i ∈ {1, . . . , k} and upd(N 00 ) = upd(N 000 ). By hypothesis (hΣ00 , I00 , I 00 i , hI00 , N 000 i) ∈ R,
hence, by definition of R, upd(N 000 ) = proj(I 00 , Σ00 ), and therefore also upd(N 00 ) = proj(I 00 , Σ00 ).
The conditions on events hold by hypothesis since function upd has no effect on DPOC
events corresponding to DIOC events. Furthermore, only enabled interactions have been
executed, hence dependencies between DPOC events corresponding to DIOC events are
untouched.
√
η
If instead hI, Ng i −
→ hI00 , N 000 i with η ∈ {o? : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), , I,
no-up, I00 , τ } then thanks to Lemma 7.21 we have one of the following: (2a) upd(Ng ) =
η
upd(N 000 ) and η ∈ {o∗ : R1 (v) → R2 (x), o∗ : R1 (X) → R2 (), τ }, or (2b) hI, upd(Ng )i −
→
η
hI00 , N 00 i such that upd(N 000 ) = upd(N 00 ). In case (2b) we have hI, upd(Ng )i −
→ hI00 , N 00 i.
η
Then, by hypothesis, we have hΣ, I, Ii −
→ hΣ00 , I00 , I 00 i and (hΣ00 , I00 , I 00 i , hI00 , N 00 i) ∈ R. To
deduce that (hΣ00 , I00 , I 00 i , hI00 , N 000 i) ∈ R, one can proceed using the same strategy as the
case of the challenge from the DIOC above. In case (2a) the step is matched by the DIOC
by staying idle, following the second option in the definition of weak system bisimulation.
The proof is similar to the one above.
Thus, we have to prove the two simplified bisimulation clauses above. The proof is
by structural induction on the DIOC I. All the subterms of a well-annotated connected
DIOC are well-annotated and connected, thus the induction can be performed. We√consider
both challenges from the DIOC (→) and from the DPOC (←). The case for label follows
from Lemma 7.22. The case for labels I is trivial. Let us consider the other labels, namely
o : R1 (v) → R2 (x), I, no-up, and τ .
Note that no transition (at the DIOC or at the DPOC level) with one of these labels
can change the set of updates I. Thus, in the following, we will not write it. Essentially, we
will use DIOC processes and DPOC networks instead of DIOC systems and DPOC systems,
respectively. Note that DPOC networks also include the state, while this is not the case
for DIOC processes. For DIOC processes, we assume to associate to them the state Σ, and
comment on its changes whenever needed.
Case 1, 0: trivial.
Case i: x@R = e: the assignment changes the global state in the DIOC, and its projection
on the role R changes the local state of the role in the DPOC in a corresponding way.
Case i: o : R1 (e) → R2 (x): trivial. Just note that at the DPOC level the interaction gives
rise to one send and one receive with the same operation and prefixed by the same index.

DYNAMIC CHOREOGRAPHIES

35

Synchronisation between send and receive is performed by Rule bDPOC |Synch e that also
removes the index from the label.
Case I; I 0 : from the definition of the projection function we have that N =kR∈roles(I;I 0 )
(π(I, R); π(I 0 , R), ΣR )R .
µ
→: Assume that I; I 0 −
→ I 00 with µ ∈ {o : R1 (v) → R2 (x); I; no-up, τ }. There are two
µ
possibilities: either (i ) I −
→ I 000 and I 00 = I 000 ; I 0 or (ii ) I has a transition with label
√
µ
and I 0 −
→ I 00 .
In case (i ) by inductive hypothesis

µ
kR∈roles(I) (π(I, R), ΣR )R −
→ N 000 and upd(N 000 ) =kR∈roles(I) π(I 000 , R), Σ0R R
Thus
 µ
kR∈roles(I) π(I, R); π(I 0 , R), ΣR R −
→ N and

000
0
upd(N ) =kR∈roles(I) π(I , R); π(I , R), Σ0R R
If roles(I 0 ) ⊆ roles(I) then the thesis follows. If roles(I 0 ) 6⊆ roles(I) then at the DPOC
level the processes in the roles in roles(I 0 ) \ roles(I) are not affected by the transition.
Note however that the projection of I on these roles is a term composed only by 1s,
and the ones corresponding to parts of I that have been consumed can be removed
by the clean part of function upd.
√
µ
In case (ii ), I has a transition with label and I 0 −
→ I 00 . By inductive hypothesis
µ
proj(I 0 , Σ) −
→ N 00 and upd(N 00 ) = proj(I 00 , Σ0 ). The thesis follows since, thanks to
µ
Lemma 7.22, proj(I; I 0 , Σ) −
→ N and upd(N ) = proj(I 00 , Σ0 ), possibly using the clean
part of function upd to remove the 1s which are no more needed.
Note that, in both the cases, conditions on events follow by inductive hypothesis.
←: Assume that
 η

N =kR∈roles(I;I 0 ) π(I, R); π(I 0 , R), ΣR R −
→kR∈roles(I;I 0 ) PR , Σ0R R
with η ∈ {o : R1 (v) → R2 (x), I, no-up, τ }. We have a case analysis on η.
If η = o : R1 (v) → R2 (x) then

i.ohvi@R2 :R1
π(I; I 0 , R1 ), ΣR1 R1 −−−−−−−−→ (PR1 , ΣR1 )R1 and
π(I; I 0 , R2 ), ΣR2

i.o(x←v)@R1 :R2


R2

−−−−−−−−−−−→ (PR2 , ΣR2 )R2

The two events have the same global index since they have the same index i (otherwise
they could not synchronise) and they are both outside of any while loop (since they
are enabled), hence the global index coincides with the index. Thus, they are either
both from I or both from I 0 .
In the first case we have also

o:R1 (v)→R2 (x)
00
kR∈roles(I;I 0 ) (π(I, R), ΣR )R −−−−−−−−−−→kR∈roles(I;I 0 ) PR
, ΣR R
o:R1 (v)→R2 (x)

00 ; π(I 0 , R). Thus, by inductive hypothesis, I −
with PR = PR
−−−−−−−−−→ I 00 and
00
00
upd(kR∈roles I;I 0 (PR , ΣR )R ) = proj(I , Σ). Hence, we have that
o:R1 (v)→R2 (x)

I; I 0 −−−−−−−−−−→ I 00 ; I 0

36

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

and

00
; π(I 0 , R), ΣR R ) = proj(I 00 ; I 0 , Σ)
upd(kR∈roles I;I 0 PR
The thesis follows.
In the second case, we need to show that the interaction o : R1 (v) → R2 (x) is
enabled. Assume that this is not the case. This means that there is a DIOC event
ε corresponding to some construct in I. Because of the definition of R, ε is also a
DPOC event and ε ≤DP OC ξ : o@R2 ∨ ε ≤DP OC ξ : o@R1 . Hence, at least one of the
two events is not minimal and the corresponding transition cannot be enabled, against
our hypothesis. Therefore the interaction o : R1 (v) → R2 (x) is enabled. Thus, I has
√
o:R1 (v)→R2 (x)
a transition with label and I 0 −−−−−−−−−−→ I 00 . Thanks to Lemma 7.22
√ then both
(π(I, R1 ), ΣR1 )R1 and (π(I, R2 ), ΣR2 )R2 have a transition with label . Thus, we
have

i.ohvi@R2 :R1
π(I 0 , R1 ), ΣR1 R1 −−−−−−−−→ (PR1 , ΣR1 )R1

i.o(x←v)@R1 :R2
π(I 0 , R2 ), ΣR2 R2 −−−−−−−−−−−→ (PR2 , ΣR2 )R2 and thus
o:R1 (v)→R2 (x)

proj(I 0 , Σ) −−−−−−−−−−→kR∈roles(I 0 ) (PR , ΣR )R
The thesis follows by inductive hypothesis.
For the other cases of η, all the roles but one are unchanged. The proof of these cases
is similar to the one for interaction, but simpler.
Note that in all the above cases, conditions on events follow by inductive hypothesis.
Case I|I 0 : from the definition of the projection function we have
N =kR∈roles(I;I 0 ) (π(I, R) | π(I 0 , R), ΣR )R
→: We have a case analysis on the rule used to derive the transition. If the transition
is derived using Rule bDIOC |Parallel e and I|I 0 can perform a transition with label
µ then one of its two components can perform a transition with the same label µ
and the thesis follows by inductive hypothesis. Additional roles not occurring in the
term performing the transition are dealt with by the clean part of function upd. If
instead the transition is derived using Rule bDIOC |Par-end e then the thesis follows
from Lemma 7.22.
←: We have a case analysis on the label η of the transition. If η = o? : R1 (v) → R2 (x)
then a send and a receive on the same operation are enabled. The two events have
the same global index since they have the same index i (otherwise they could not
synchronise) and they are both outside of any while loop (since they are enabled),
hence the global index coincides with the index. Thus, they are either both from I or
both from I 0 . The thesis follows by inductive hypothesis. For the other cases of η,
only the process of one role changes. The thesis follows by inductive hypothesis. In
all the cases, roles not occurring in the term performing the transition are dealt with
by function upd.

DYNAMIC CHOREOGRAPHIES

37

Case i: if b@R {I} else {I 0 }: from the definition of projection


 
N = kS∈roles(I,I 0 )r{R} i? : i.cnd∗i : xi from R; i: if xi {π(I, S)} else {π(I 0 , S)}, ΣS
k
S





Y
iT : i.cnd∗i : true to R0  ; π(I, R)
i: if b 


R0 ∈roles(I,I 0 )r{R}



!


Y
iF : i.cnd∗i : false to R0  ; π(I 0 , R) , ΣR
else 


R
R0 ∈roles(I,I 0 )r{R}
Let us consider the case when the guard is true (the other one is analogous).
τ
→: The only possible transition from the DIOC is i: if b@R {I} else {I 0 } −
→ I. The
DPOC can match this transition by reducing to


 
i? : i.cnd∗i : xi from R;
0
N = kS∈roles(I,I 0 )r{R}
, ΣS
k
i: if xi {π(I, S)} else {π(I 0 , S)}
S



Y

iT : i.cnd∗i : true to R0  ; π(I, R), ΣR 
R0 ∈roles(I,I 0 )r{R}
R
By applying function upd we get


upd(N 0 ) = kS∈roles(I,I 0 )r{R} (π(I, S), ΣS )S k (π(I, R), ΣR )R
Concerning events, at the DIOC level events corresponding to the guard and to the
discarded branch are removed. The same holds at the DPOC level, thus conditions
on the remaining events are inherited. This concludes the proof.
←: The only possible transition from the DPOC is the evaluation of the guard from
the coordinator. This reduces N to N 0 above and the thesis follows from the same
reasoning.
Case i: while b@R {I}: from the definition of projection


 
i? : i.wb∗i : xi from R; i: while xi {π(I, S);
N = kS∈roles(I)r{R}
, ΣS
k
iC : i.we∗i : ok to R; i? : i.wb∗i : xi from R}
S
!

 

Q




 
iT : i.wb∗i : true to R0 ; π(I, R); 





R0 ∈roles(I)r{R}
; 
 i: while b
Q









iC : i.we∗i : from R0
 



R0 ∈roles(I)r{R}




Q


iF : i.wb∗i : false to R0 , ΣR
R0 ∈roles(I)r{R}
R
→: Let us consider the case when the guard is true. The only possible transition from
τ
the DIOC is i: while b@R {I} −
→ I; i: while b@R {I}. The DPOC can match this

38

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

transition by reducing to


0

N =kS∈roles(I)r{R}



i? : i.wb∗i : xi from R; i: while xi {π(I, S);
, ΣS
k
iC : i.we∗i : ok to R; i? : i.wb∗i : xi from R}
S
!


Q
iT : i.wb∗i : true to R0 ; π(I, R);

 R0 ∈roles(I)r{R}
!


Q

iC : i.we∗i : from R0 ;

 R0 ∈roles(I)r{R}


!


Q


∗
0


iT : i.wbi : true to R ; π(I, R);


R0 ∈roles
(I)r{R}
 i: while b
Q



iC : i.we∗i : from R0


 0

R ∈roles(I)r{R}


Q

iF : i.wb∗i : false to R0 , ΣR
0
R ∈roles(I)r{R}
By applying function upd we get




R0 ∈

;

R



k



π(I, R);




 i: while b






Q








π(I, S); i? : i.wb∗i : xi from R;

 i: while xi {π(I, S);

, ΣS 

 iC : i.we∗i : ok to R;
∗
i? : i.wbi : xi from R}
S



upd(N 0 ) = 
 kS∈roles(I)r{R}





































Q
R0 ∈roles
Q (I)r{R}
R0 ∈roles(I)r{R}

roles(I)r{R}


!


iT : i.wb∗i : true to R0 ; π(I, R); 


iC : i.we∗i : from R0

iF : i.wb∗i : false to R0






;






, ΣR 





R

exactly the projection of I; i: while b@R {I}.
As far as events are concerned, in compl(N 0 ) we have all the needed events since, in
particular, we have already done the unfolding of the while in all the roles. Concerning
the ordering, at the DIOC level, we have two kinds of causal dependencies: (1) events
in the unfolded process precede the guard event; (2) the guard event precedes the
events in the body. The first kind of causal dependency is matched at the DPOC
level thanks to the auxiliary synchronisations that close the unfolded body (which
are not removed by compl) using synchronisation and sequentiality. The second kind
of causal dependency is matched thanks to the auxiliary synchronisations that start
the following iteration using synchronisation, sequentiality and while.
The case when the guard evaluates to false is simpler.
←: The only possible transition from the DPOC is the evaluation of the guard from
the coordinator. This reduces N to N 0 above and the thesis follows from the same
reasoning.

DYNAMIC CHOREOGRAPHIES

39

Case i: scope @R {I}: from the definition of the projection

 
N = kR0 ∈roles(I)r{R} i: scope @R {π(I, R0 )}, ΣR0 R0 k
(i: scope @R {π(I, R)} roles {roles(I)}, ΣR )R
→: Let us consider the case when the scope is updated. At the DIOC level all the
possible transitions have label of the form I 0 and are obtained by applying Rule
bDIOC |Up e. Correspondingly, at the DPOC level one applies Rule bDPOC |Lead-Up e to
the coordinator of the update, obtaining

 
N 0 = kR0 ∈roles(I)r{R} i: scope @R {π(I, R0 )}, ΣR0 R0 k
!


Q
∗
0
0
0
i.sbi : π(I , R ) to R ;


 R0 ∈roles(I)r{R}




, ΣR 
 π(I 0 , R);



Q


i.se∗i : from R0
R0 ∈roles(I)r{R}
R
By applying the upd function we get:

 

upd(N 0 ) = kR0 ∈roles(I)r{R} π(I 0 , R0 ), ΣR0 R0 k π(I 0 , R), ΣR R
This is exactly the projection of the DIOC obtained after applying the rule bDIOC |Up e.
The conditions on events are inherited. Observe that the closing event of the scope is
replaced by events corresponding to the auxiliary interactions closing the scope. This
allows us to preserve the causality dependencies also when the scope is inserted in a
context.
The case of Rule bDIOC |NoUp e is simpler.
←: The only possible transitions from the DPOC are the ones of the coordinator of the
update checking whether to apply an update or not. This reduces N to N 0 above
and the thesis follows from the same reasoning.
7.2. Deadlock freedom, termination, and race freedom. Due to the fact that the
projection preserves weak traces, we have that trace-based properties of the DIOC are
inherited by the DPOC. A first example of such properties is deadlock freedom.
Definition 7.23 (Deadlock freedom). An internal DIOC (resp. DPOC) trace is obtained
by removing transitions labelled I from a DIOC (resp. DPOC) trace. √
A DIOC (resp. DPOC)
system is deadlock free if all its maximal finite internal traces have as last label.
Intuitively, internal traces are needed since labels I do not correspond to activities of
the
application
and may be executed also after application termination. The fact that after
√
a only changes in the set of available updates are possible is captured by the following
lemma.
Lemma √7.24. For each initial, connected DIOC I, state Σ, and set of updates I, if
hΣ, I, Ii −
→ hΣ0 , I0 , I 0 i then each transition of hΣ0 , I0 , I 0 i has label I00 for some I00 .
Proof. The proof is by case analysis on the rules which can derive a transition with label
All the cases are easy.

√

.

40

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

Since by construction initial DIOCs are deadlock free we have that also the DPOC
obtained by projection is deadlock free.
Corollary 7.25 (Deadlock freedom). For each initial, connected DIOC I, state Σ, and set
of updates I the DPOC system hI, proj(I, Σ)i is deadlock free.
Proof. Let us first prove that for each initial, connected DIOC I, state Σ, and set of updates
I, the DIOC system hΣ, I, Ii
√ is deadlock free. This amounts to prove that all its maximal
finite internal traces have as last label. For each trace, the proof is by induction on its
length, and for each length by structural induction on I. The proof is based on the fact
that I is initial. The induction considers a reinforced hypothesis, saying also that:
√
•
may occur only as the last label of the internal trace;
• all the DIOC systems in the sequence of transitions generating the trace, but the last one,
are initial.
We have a case analysis on the top-level operator in I. Note that in all the cases, but 0, at
least a transition is derivable.
Case 0: not allowed since we assumed an initial DIOC.
√
Case 1: trivial because by Rule bDIOC |End e and Lemma 7.24 its only internal trace is .
Case x@R = e: the only applicable rule is bDIOC |Assign e that in one step leads to a 1
process. The thesis follows by inductive hypothesis on the length of the trace.
Case o? : R1 (e) → R2 (x): the only applicable rule is bDIOC |Interaction e, which leads to an
assignment. Then the thesis follows by inductive hypothesis on the length of the trace.
Case I; I 0 : the first transition can be derived either by Rule bDIOC |Sequence e or Rule
bDIOC |Seq-end e. In the first case the thesis follows by induction on the length of the
trace. In the second case the trace coincides with a trace of I 0 , and the thesis follows by
structural induction.
Case I|I 0 : the first transition can be derived either by Rule bDIOC |Parallel e or by Rule
[Par-End]. In the first case the thesis follows by induction on the length
√ of the trace.
In the second case the thesis follows by Lemma 7.24, since the label is .
Case if b@R {I} else {I 0 }: the first transition can be derived using either Rule
bDIOC |If-then e or Rule bDIOC |If-else e. In both the cases the thesis follows by induction
on the length of the trace.
Case while b@R {I}: the first transition can be derived using either Rule
bDIOC |While-unfold e or Rule bDIOC |While-exit e. In both the cases the thesis follows by
induction on the length of the trace.
Case scope @R {I}: the first transition can be derived using either Rule bDIOC |Up e or
Rule bDIOC |NoUp e. In both the cases the thesis follows by induction on the length of the
trace.
The weak internal traces of the DIOC coincide with the weak internal traces of the√DPOC
by Theorem 7.2, thus also the finite weak internal traces of √
the DPOC end with . The
same holds for the finite strong internal traces, since label
is preserved when
√ moving
between strong and weak traces, and no transition can be added after the
thanks to
Lemma 7.24.
DPOCs also inherit termination from terminating DIOCs.
Definition 7.26 (Termination). A DIOC (resp. DPOC) system terminates if all its internal
traces are finite.

DYNAMIC CHOREOGRAPHIES

41

Note that if arbitrary sets of updates are allowed, then termination of DIOCs that
contain at least a scope is never granted. Indeed, the scope can always be replaced by a
non-terminating update or it can trigger an infinite chain of updates. Thus, to exploit this
result, one should add constraints on the set of updates ensuring DIOC termination.
Corollary 7.27 (Termination). If the DIOC system hΣ, I, Ii terminates and I is connected
then the DPOC system hI, proj(I, Σ)i terminates.
Proof. It follows from the fact that only a finite number of auxiliary actions are added when
moving from DIOCs to DPOCs.
Other interesting properties derived from weak trace equivalence are freedom from races
and orphan messages. A race occurs when the same receive (resp. send) may interact with
different sends (resp. receives). In our setting, an orphan message is an enabled send that is
never consumed by a receive. Orphan messages are more relevant in asynchronous systems,
where a message may be sent, and stay forever in the network, since the corresponding
receive operation may never become enabled. However, even in synchronous systems
orphan messages should be avoided: the message is not communicated since the receive
is not available, hence a desired behaviour of the application never takes place due to
synchronisation problems. Trivially, DIOCs avoid races and orphan messages since send and
receive are bound together in the same construct. Differently, at the DPOC level, since all
receive of the form ι: i.o? : x from R1 in role R2 may interact with the sends of the form
ι: i.o? : e to R2 in role R1 , races may happen. However, thanks to the correctness of the
projection, race freedom holds also for the projected DPOCs.
Corollary 7.28 (Race freedom). For each initial, connected DIOC I, state Σ, and set
η1
ηn
0
?
∗
of updates I, if hI,
√ proj(I, Σ)i −→ · · · −→ hI , N i, where ηi ∈ {τ, o : R1 (v) → R2 (x), o :
R1 (X) → R2 (), , I, no-up, I} for each i ∈ {1, . . . , n}, then in N there are no two sends
(resp. receives) which can interact with the same receive (resp. send).
Proof. We have two cases, corresponding respectively to programmer-specified and auxiliary
operations.
For programmer-specified operations, thanks to Lemma 7.20, case C1, for each global
index ξ there are at most two communication events with global index ξ. The corresponding
DPOC terms can be enabled only if they are outside of the body of a while loop. Hence,
their index coincides with their global index. Since the index prefixes the operation, then no
interferences with other sends or receives are possible.
For auxiliary operations, the reasoning is similar. Note, in fact, that sends or receives with
the same global index can be created only by a unique DIOC construct, but communications
between the same pair of roles are never enabled together. This can be seen by looking at
the definition of the projection.
As far as orphan messages are concerned, they may appear in infinite DPOC computations since a receive may not become enabled due to an infinite loop. However, as a corollary
of trace equivalence, we have that terminating DPOCs are orphan-message free.
Corollary 7.29 (Orphan-message freedom). For each
initial, connected DIOC I, state Σ,
√
η1

ηn

and set of updates I, if hI,√
proj(I, Σ)i −→ · · · −→−
→ hI0 , N i, where ηi ∈ {τ, o? : R1 (v) →
∗
R2 (x), o : R1 (X) → R2 (), , I, no-up, I}, then N contains no sends.
√
Proof. The proof is by case analysis on the rules which can derive a transition with label .
All the cases are easy.

42

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

8. Adaptable Interaction-Oriented Choreographies in Jolie
In this section we present AIOCJ (Adaptable Interaction-Oriented Choreographies in Jolie),
a development framework for adaptable distributed applications [28]. AIOCJ is one of the
possible instantiations of the theoretical framework presented in the previous sections and
it gives a tangible proof of the expressiveness and feasibility of our approach. We say that
AIOCJ is an instance of our theory because it follows the theory, but it provides mechanisms
to resolve the non-determinism related to the choice of whether to update or not and on
which update to select. Indeed, in AIOCJ updates are chosen and applied according to the
state of the application and of its running environment. To this end, updates are embodied
into adaptation rules, which specify when and whether a given update can be applied, and to
which scopes. AIOCJ also inherits all the correctness guarantees provided by our theory, in
particular: i ) applications are free from deadlocks and races by construction, ii ) applications
remain correct after any step of adaptation. As in the theory, adaptation rules can be added
and removed while applications are running.
Remark 8.1. In order for the correctness guarantees to be provided, one needs to satisfy
the required assumptions, in particular the fact that functions never block and always return
a value (possibly an error notification). If this condition is not satisfied, at the theoretical
level, the behaviour of the source DIOC and the behaviour of its projection may differ,
as described in Remark 2.2. The behaviour of the corresponding AIOCJ application can
be different from both of them. Usually, the violation of the assumption above leads the
application to crash. This allows the programmer to realise that the assumption has been
violated.
Below we give a brief overview of the AIOCJ framework by introducing its components:
the Integrated Development Environment (IDE), the AIOCJ compiler, and the Runtime
Environment.
Integrated Development Environment. AIOCJ supports the writing of programs and adaptation rules in the Adaptable Interaction-Oriented Choreography (AIOC) language, an
extension of the DIOC language. We discuss the main novelties of the AIOC language in
§ 8.1. AIOCJ offers an integrated environment for developing programs and adaptation
rules that supports syntax highlighting and on-the-fly syntax checking. Since checking
for connectedness (see § 6) of programs and adaptation rules is polynomial (as proven by
Theorem 6.3), the IDE also performs on-the-fly checks on connectedness of programs and
rules.
Compiler . The AIOCJ IDE also embeds the AIOCJ compiler, which implements the procedure for projecting AIOCs and adaptation rules into distributed executable code. The
implementation of the compiler is based on the rules for projecting DIOCs, described in § 4.
The target language of the AIOCJ compiler is Jolie [26, 35], a Service-Oriented language
with primitives similar to those of our DPOC language. Jolie programs are also called
services. Given an AIOC program, the AIOCJ compiler produces one Jolie service for each
role in the source AIOC. The compilation of an AIOC rule produces one Jolie service for
each role and an additional service that describes the applicability condition of the rule. All
these services are enclosed into an Adaptation Server, described below.

DYNAMIC CHOREOGRAPHIES

43

Runtime Environment. The AIOCJ runtime environment comprises a few Jolie services
that support the execution and adaptation of compiled programs. The main services of
the AIOCJ runtime environment are the Adaptation Manager, Adaptation Servers, and the
Environment. The compiled services interact both among themselves and with an Adaptation
Manager, which is in charge of managing the adaptation protocol. Adaptation Servers
contain adaptation rules, and they can be added or removed dynamically, thus enabling
dynamic changes in the set of rules, as specified by Rule bDIOC |Change-Updates e. When
started, an Adaptation Server registers itself at the Adaptation Manager. The Adaptation
Manager invokes the registered Adaptation Servers to check whether their adaptation rules
are applicable. In order to check whether an adaptation rule is applicable, the corresponding
Adaptation Server evaluates its applicability condition. Applicability conditions may refer
to the state of the role which coordinates the update, to properties of the scope, and to
properties of the environment (e.g., time, temperature, etc.), stored in the Environment
service.
In the remainder of this Section we detail the grammar of the AIOC language used by
AIOCJ in § 8.1, we illustrate the use of AIOCJ on a simple example in § 8.2, we discuss
some relevant implementation aspects of AIOCJ in § 8.3, and we present some guidelines on
how to use scopes in AIOCJ in § 8.4.
8.1. DIOC Language Extensions in AIOCJ. AIOCs extend DIOCs with:
• the definition of adaptation rules, instead of updates, that include the information needed
to evaluate their applicability condition;
• the definition of constructs to express the deployment information needed to implement
real-world distributed applications.
Below we describe in detail, using the Extended Backus-Naur Form [3], the new or refined
constructs introduced by the AIOC language.
Function inclusions. The AIOC language can exploit functionalities provided by external
services via the include construct. The syntax is as follows.
Include ::= include FName [ , FName ]* from " URL " [ with PROTOCOL ]

This allows one to reuse existing legacy code and to interact with third-party external
applications. As an example, the Seller of our running example can exploit an external
database to implement the functionality for price retrieval getPrice, provided that such a
functionality is exposed as a service. If the service is located at "socket://myService:8000"
and accessible via the "SOAP" protocol we enable its use with the following inclusion:
include getPrice from " socket :// myService :8000 " with " SOAP "

Similarly, the Bank IT system is integrated in the example by invoking the function
makePayment, also exposed as a service.

This feature enables a high degree of integration since AIOCJ supports all protocols
provided by the underlying Jolie language, which include TCP/IP, RMI, SOAP, XML/RPC,
and their encrypted correspondents over SSL.
External services perfectly fit the theory described in previous sections, since they are
seen as functions, and thus introduced in expressions. Notice, in particular, that Remark 8.1
applies.
Adaptation rules. Adaptation rules extend DIOC updates, and are a key ingredient of
the AIOCJ framework. The syntax of adaptation rules is as follows:

44

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

Rule ::= rule {
[ Include ]*
on { Condition }
do { Choreography }
}

The applicability condition of the adaptation rule is specified using the keyword on,
while the code to install in case adaptation is performed (which corresponds to the DIOC
update) is specified using the keyword do. Optionally, adaptation rules can include functions
they rely on.
The Condition of an adaptation rule is a propositional formula which specifies when the
rule is applicable. To this end, it can exploit three sources of information: local variables of
the coordinator of the update, environmental variables, and properties of the scope to which
the adaptation rule is applied. Environmental variables are meant to capture contextual
information that is not under the control of the application (e.g., temperature, time, available
resources, . . . ). To avoid ambiguities, local variables of the coordinator are not prefixed,
environment variables are prefixed by E, and properties of the scope are prefixed by N.
For example, if we want to apply an adaptation rule only to those scopes whose property
name is equal to the string "myScope" we can use as applicability condition the formula
N.name == "myScope".
Scopes. As described above, scopes in AIOC also feature a set of properties (possibly
empty). Scope properties describe the current implementation of the scope, including both
functional and non-functional properties. Such properties are declared by the programmer,
and the system only uses them to evaluate the applicability condition of adaptation rules,
to decide whether a given adaptation rule can be applied to a given scope. Thus the syntax
for scopes in AIOC is:
scope @ Role { Choreography }
[ prop { Properties } ]?

where clause prop introduces a list of comma-separated assignments of the form
N.ID = Expression.
For instance, the code
scope @ R {
// AIOC code
} prop { N . name = " myScope " }
specifies that the scope has a property name set to the string "myScope", thus satisfying the
applicability condition N.name == "myScope" discussed above.
Programs. AIOC programs have the following structure.
Program ::=
[ Include ]*
preamble {
starter : Role
[ Location ]*
}
aioc { Choreography }

DYNAMIC CHOREOGRAPHIES

45

where Include allows one to include external functionalities, as discussed above, and
keyword aioc introduces the behaviour of the program, which is a DIOC apart for the fact
that scopes may define properties, as specified above.
The keyword preamble introduces deployment information, i.e., the definition of the
starter of the AIOC and the Location of participants.
The definition of a starter is mandatory and designs which role is in charge of waiting
for all other roles to be up and running before starting the actual computation. Any role
can be chosen as starter, but the chosen one needs to be launched first when running the
distributed application.
Locations define where the participants of the AIOC will be deployed. They are specified
using the keyword location:
Location ::= location @ Role : " URL "

where Role is the name of a role (e.g., Role1) and URL specifies where the service
can be found (e.g., "socket://Role1:8001"). When not explicitly defined, the projection
automatically assigns a distinct local TCP/IP location to each role.
8.2. AIOCJ Workflow. Here we present a brief description of how a developer can write
an adaptable distributed system in AIOCJ, execute it, and change its behaviour at runtime
by means of adaptation rules. For simplicity, we reuse here the minimal example presented
in the Introduction, featuring a scope that encloses a price offer from the Seller to the
Buyer and an update — here an adaptation rule — that provides a discount for the Buyer.
We report the AIOC program in the upper part and the adaptation rule in the lower part of
Figure 13.
At Line 1 of the AIOC program we have the inclusion of function getPrice, which is
provided by a service within the internal network of the Seller, reachable as a TCP/IP node
at URL "storage.seller.com" on port "80". At Line 2 of the AIOC program we have the
preamble. The preamble specifies deployment information, and, in particular, defines the
starter, i.e., the service that ensures that all the participants are up and running before
starting the actual computation. No locations are specified, thus default ones are used.
The actual code is at Lines 4–7, where we declare a scope. At Line 7 we define a property
scope_name of this scope with value "price_inquiry".
1 and execution ○
2 of the AIOC. From
Figure 14 depicts the process of compilation ○
left to right, we write the AIOC and we compile it into a set of executable Jolie services
(Buyer service and Seller service). To execute the projected system, we first launch the
Adaptation Manager and then the two compiled services, starting from the Seller, which is
the starter. Since there is no compiled adaptation rule, the result of the execution is the
offering of the standard price to the Buyer.
Now, let us suppose that we want to adapt our system to offer discounts in the Fall
season. To do that, we can write the adaptation rule shown in the lower part of Figure 13.
Since we want to replace the scope for the price_inquiry, we define, at Line 4, that this
rule applies only to scopes with property scope_name set to "price_inquiry". Furthermore,
since we want the update to apply only in the Fall season, we also specify that the environment
variable E.season should match the value "Fall". The value of E.season is retrieved from the
Environment Service.
The rule uses two functions. At Line 2, it includes function getPrice, which is the one
used also in the body of the scope. The other function, isValid, is included at Line 3 and

46

1
2
3
4
5
6
7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

include getPrice from " socket :// storage . seller . com :80 "
preamble { starter : Seller }
aioc {
scope @ Seller {
order_price @ Seller = getPrice ( order ) ;
offer : Seller ( order_price ) -> Buyer ( prod_price )
} prop { N . scope_name = " price_inquiry " } }

rule {
include getPrice from " socket :// storage . seller . com :80 "
include isValid from " socket :// discounts . seller . com :80 "
on { N . scope_name == " price_inquiry " and E . season == " Fall " }
do {
cardReq : Seller ( _ ) -> Buyer ( _ ) ;
card_id @ Buyer = getInput ( " Insert your customer card ID " ) ;
cardRes : Buyer ( card_id ) -> Seller ( buyer_id ) ;
if isValid ( buyer_id ) @ Seller {
order_price @ Seller = getprice ( order )*0.9 ;
} else {
order_price @ Seller = getPrice ( order )
};
offer : Seller ( order_price ) -> Buyer ( prod_price )
}
}

Figure 13: An AIOC program (upper part) and an applicable adaptation rule (lower part).
it is provided by a different TCP/IP node, located at URL "discounts.seller.com" on port
"80" within the internal network of the Seller.
The body of the adaptation rule (Lines 6–14) specifies the same behaviour described
in Figure 1 in the Introduction: the Seller asks the Buyer to provide its card_id, which
the Seller uses to provide a discount on the price of the ordered product. We depict
the inclusion of the new adaptation rule (outlined with dashes) and the execution of the
3 of Figure 14. From right to left, we write the rule and we compile
adaptation at point ○
it. The compilation of a (set of) adaptation rule(s) in AIOCJ produces a service, called
Adaptation Server (also outlined with dashes), that the Adaptation Manager can query to
fetch adaptation rules at runtime. The compilation of the adaptation rule can be done while
the application is running. After the compilation, the generated Adaptation Server is started
and registers on the Adaptation Manager. Since the rule relies on the environment to check
its applicability condition, we also need the Environment service to be running. In order for
the adaptation rule to apply we need the environment variable season to have value "Fall".
8.3. Implementation. AIOCJ is composed of two elements: the AIOCJ Integrated Development Environment (IDE), named AIOCJ − ecl, and the adaptation middleware that
enables AIOC programs to adapt, called AIOCJ − mid.

DYNAMIC CHOREOGRAPHIES

47

Runtime Environment
2

Adaptation
Manager

Compilation on
role Buyer

AIOC

Buyer service

3

Adaptation
Server

1

Compilation

Adaptation
Rules

Compilation on
role Seller

AIOC Language

Seller service
Environment
service

Jolie Language

AIOC Language

Figure 14: Representation of the AIOCJ framework — Projection and execution of the
example in Figure 13.

Figure 15: Check for connectedness.
AIOCJ − ecl is a plug-in for Eclipse [21] based on Xtext [49]. Starting from a grammar,
Xtext generates the parser for programs written in the AIOC language. Result of the parsing
is an abstract syntax tree (AST) we use to implement i ) the checker of connectedness for
AIOC programs and adaptation rules and ii ) the generation of Jolie code for each role. Since
the check for connectedness has polynomial computational complexity (cf. Theorem 6.3)
it is efficient enough to be performed while editing the code. Figure 15 shows AIOCJ − ecl
notifying the error on the first non-connected instruction (Line 13).

48

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

As already mentioned, we chose Jolie as target language of the compilation of AIOCJ
because its semantics and language constructs naturally lend themselves to translate our
theoretical results into practice. Indeed, Jolie supports architectural primitives like dynamic
embedding, aggregation, and redirection, which ease the compilation of AIOCs.
Each scope at the AIOC level is projected into a specific sub-service for each role. The
roles run the projected sub-services by embedding them and access them via redirection. In
this way, we implement adaptation by disabling the default sub-service and by redirecting
the execution to a new one, obtained from the Adaptation server.
When at runtime the coordinator of the update reaches the beginning of that scope, it
queries the Adaptation Manager for adaptation rules to apply. The Adaptation Manager
queries each Adaptation Server sequentially, based on their order of registration. On its
turn, each Adaptation Server checks the applicability condition of each of its rules. The first
rule whose applicability condition holds is applied. The adaptation manager sends to the
coordinator the updates that are then distributed to the other involved roles. In each role,
the new code replaces the old one.
To improve the performance, differently from the theory, in AIOCJ adaptation rules are
compiled statically, and not by the coordinator of the update when the update is applied.
8.4. AIOCJ Practice. AIOCJ provides scopes as a way to specify which parts of the
application can be updated. As a consequence, deciding which parts of the code to enclose
in scopes is a relevant and non trivial decision. Roughly, one should enclose into scopes parts
of the code that may need to be updated in the future. This includes for instance parts of
the code which model business rules, hence may change according to business needs, parts
of the code which are location dependent, hence may be updated to configure the software
for running in different locations, parts of the code which are relevant for performance or
security reasons, hence may be updated to improve the performance or the security level.
One may think that a simple shortcut would be to have either a big scope enclosing the
whole code of the application or many small scopes covering all the code, but both these
solutions have relevant drawbacks. Indeed, if one replaces a big scope in order to change a
small piece of it, (s)he has to provide again all the code, while one would like to provide only
the part that needs to change. Furthermore, update for the big scope is no more available
as soon as its execution starts, which may happen quite earlier than when the activity to
be updated starts. Using small scopes also is not a solution, since an update may need to
cover more than one such scope, but there is no way to ensure that multiple scopes are
updated in a coordinated way. Also, both the approaches have performance issues: in the
first case large updates have to be managed, in the second case many checks for the updates
are needed, causing a large overhead.
In order to write updates for a given scope, one needs to have some knowledge about
the scope that the update is going to replace, since the update will run in the context where
the scope is. This includes, for instance, knowing which variables are available, their types
and their meaning, and in which variables results are expected. This information can be
either tracked in the documentation of the application, or added to the scope properties.
In this way, the adaptation rule embodying the update can check this information before
applying the update (see for instance the approach of [29]). The fact that this information
is needed for all scopes is another point against the approach of using many small scopes.

DYNAMIC CHOREOGRAPHIES

49

9. Related work and discussion
Recently, languages such as Rust [44] or SCOOP [41] have been defined to provide highlevel primitives to program concurrent applications avoiding by construction some of the
risks of concurrent programming. For instance, Rust ensures that there is exactly one
binding to any given resource using ownership and borrowing mechanisms to achieve memory
safety. SCOOP instead provides the separate keyword to enable programming patterns
that enforce data-race freedom. In industry, Rust has started to be used for the development
of complex concurrent/distributed systems (e.g., the file storage system of Dropbox [33] or
the parallel rendering engine of Mozilla [51]). However, industry has not yet widely adopted
any language-based solution trading expressive power of the language for safety guarantees.
Inspired by the languages above, we have presented high-level primitives for the dynamic
update of distributed applications. We guarantee the absence of communication deadlocks
and races by construction for the running distributed application, even in presence of updates
that were unknown when the application was started. More generally, the compilation of a
DIOC specification produces a set of low-level DPOCs whose behaviour is compliant with
the behaviour of the originating DIOC.
As already remarked, our theoretical model is very general. Indeed, whether to update a
scope or not and which update to apply if many are available is completely non deterministic.
Choosing a particular policy for decreasing the non-determinism of updates is orthogonal
with respect to our results. Our properties are preserved by any such policy, provided that
the same policy is applied both at the DIOC and at the DPOC level. AIOCJ presents
a possible instantiation of our general approach with a concrete mechanism for choosing
updates according to the state of the application and of its running environment.
Our work is on the research thread of choreographies and multiparty session types [12,
24, 13, 14, 5, 45]. One can see [25] for a description of the field. Like choreographies and
multiparty session types, DIOCs target communication-centred concurrent and distributed
applications, avoiding deadlocks and communication races. Thanks to the particular structure
of the language, DIOCs provide the same guarantees without the need of types. Below we
just discuss the approaches in this research thread closest to ours. The two most related
approaches we are aware of are based on multiparty session types, and deal with dynamic
software updates [2] and with monitoring of self-adaptive systems [16]. The main difference
between [2] and our approach is that [2] targets concurrent applications which are not
distributed. Indeed, it relies on a check on the global state of the application to ensure
that the update is safe. Such a check cannot be done by a single role, thus it is impractical
in a distributed setting. Furthermore, the language in [2] is much more constrained than
ours, e.g., requiring each pair of participants to interact on a dedicated pair of channels, and
assuming that all the roles that are not the sender or the receiver within a choice behave
the same in the two branches. The approach in [16] is very different from ours, too. In
particular, in [16], all the possible behaviours are available since the very beginning, both at
the level of types and of processes, and a fixed adaptation function is used to switch between
them. This difference derives from the distinction between self-adaptive applications, as
they discuss, and applications updated from the outside, as in our case.
We also recall [20], which uses types to ensure safe adaptation. However, [20] allows
updates only when no session is active, while we change the behaviour of running DIOCs.
We highlight that, contrarily to our approach, none of the approaches above has been
implemented.

50

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

Various tools [17, 4, 8] support adaptation exploiting automatic planning techniques in
order to elaborate, at runtime, the best sequence of activities to achieve a given goal. These
techniques are more declarative than ours, but, to the best of our knowledge, they are not
guaranteed to always find a plan to adapt the application.
[38] presents an approach to safe dynamic software updates for concurrent systems.
According to [38], safe means that all the traces are version consistent, namely that for each
trace there is a version of the application able to produce it. In our case, we want the effects
of the update to be visible during the computation, hence we do not want this property to
hold. Instead, for us safe means that the DIOC and the projected DPOC are weak system
bisimilar, and that they are both free from deadlocks and races.
Among the non-adaptive languages, Chor [13] is the closest to ours. Indeed, like ours,
Chor is a choreographic language that compiles to Jolie. Actually, AIOCJ shares part of
the Chor code base. Our work shares with [37] the interest in choreographies composition.
However, [37] uses multiparty session types and only allows static parallel composition, while
we replace a term inside an arbitrary context at runtime.
Extensions of multiparty session types with error handling [11, 9] share with us the
difficulties in coordinating the transition from the expected pattern to an alternative one, but
in their case the error recovery pattern is known since the very beginning, thus considerably
simplifying the analysis.
We briefly compare to some works that exploit choreographic descriptions for adaptation,
but with very different aims. For instance, [27] defines rules for adapting the specification
of the initial requirements for a choreography, thus keeping the requirements up-to-date in
presence of run-time changes. Our approach is in the opposite direction: we are not interested
in updating the system specification tracking system updates, but in programming and
ensuring correctness of adaptation itself. Other formal approaches to adaptation represent
choreographies as annotated finite state automata. In [43] choreographies are used to
propagate protocol changes to the other peers, while [48] presents a test to check whether
a set of peers obtained from a choreography can be reconfigured to match a second one.
Differently from ours, these works only provide change recommendations for adding and
removing message sequences.
An approach close to ours is multi-tier programming [39, 6, 15], where the programmer
writes a single program that is later automatically distributed to different tiers. This is
similar to what we do by projecting a DIOC on the different roles. In particular, [39]
considers functional programs with role annotations and splits them into different sequential
programs to be run in parallel. Multi-tier approaches such as HipHop [6] or Link [15]
have been implemented and used to develop three tier web applications. Differently from
ours, these works abstract away communication information as much as possible, while
we emphasise this kind of information. Furthermore, they do not take into account code
update. It would be interesting to look for cross-fertilisation results between our approach
and multi-tier programming. For instance, one could export our techniques to deal with
runtime updates into multi-tier programming. In the other direction, we could abstract
away communications and let the compiler manage them according to the programmed flow
of data, as done in multi-tier programming. For instance, in Figure 2 the communications
at Lines 22, 24, and 26 could be replaced by local assignments, since the information on the
chosen branch is carried by the auxiliary communications. In general, communications seem
not strictly needed from a purely technical point of view, however they are relevant for the
systems we currently consider. Furthermore, the automatic introduction of communications

DYNAMIC CHOREOGRAPHIES

51

in an optimised way is not always trivial since the problem is NP-hard even for languages
that do non support threads [40].
On a broader perspective, our theory can be used to inject guarantees of freedom
from deadlocks and races into many existing approaches to adaptation, e.g., the ones in
the surveys [32, 22]. However, this task is cumbersome, due to the huge number and
heterogeneity of those approaches. For each of them the integration with our techniques is
far from trivial. Nevertheless, we already started it. Indeed, AIOCJ follows the approach to
adaptation described in [29]. However, applications in [29] are not distributed and there
are no guarantees on the correctness of the application after adaptation. Furthermore, in
the website of the AIOCJ project [1], we give examples of how to integrate our approach
with distributed [42] and dynamic [50] Aspect-Oriented Programming (AOP) and with
Context-Oriented Programming (COP) [23]. In general, we can deal with cross-cutting
concerns like logging and authentication, typical of AOP, viewing pointcuts as empty scopes
and advices as updates. Layers, typical of COP, can instead be defined by updates which can
fire according to contextual conditions. As future work, besides applying the approach to
other adaptation mechanisms, we also plan to extend our techniques to deal with multiparty
session types [12, 24, 13, 14]. The main challenge here is to deal with multiple interleaved
sessions whilst each of our choreographies corresponds to a single session. An initial analysis
of the problem is presented in [7].
Also the study of more refined policies for rule selection, e.g., based on priorities, is a
topic for future work.
References
[1] AIOCJ website. http://www.cs.unibo.it/projects/jolie/aiocj.html.
[2] G. Anderson and J. Rathke. Dynamic software update for message passing programs. In APLAS, volume
7705 of LNCS, pages 207–222. Springer, 2012.
[3] J. W. Backus. The syntax and semantics of the proposed international algebraic language of the zurich
ACM-GAMM conference. In IFIP Congress, pages 125–131, 1959.
[4] L. Baresi, A. Marconi, M. Pistore, and A. Sirbu. Corrective Evolution of Adaptable Process Models. In
BMMDS/EMMSAD, volume 147 of LNBIP, pages 214–229. Springer, 2013.
[5] S. Basu, T. Bultan, and M. Ouederni. Deciding choreography realizability. In POPL, pages 191–202.
ACM, 2012.
[6] G. Berry and M. Serrano. Hop and HipHop: Multitier Web Orchestration. In ICDCIT, volume 8337 of
LNCS, pages 1–13. Springer, 2014.
[7] M. Bravetti et al. Towards global and local types for adaptation. In SEFM Workshops, volume 8368 of
LNCS, pages 3–14. Springer, 2013.
[8] A. Bucchiarone, A. Marconi, C. A. Mezzina, M. Pistore, and H. Raik. On-the-fly adaptation of dynamic
service-based systems: Incrementality, reduction and reuse. In ICSOC, volume 8274 of LNCS, pages
146–161. Springer, 2013.
[9] S. Capecchi, E. Giachino, and N. Yoshida. Global Escape in Multiparty Sessions. In Proc. of FSTTCS
2010, volume 8 of LIPIcs, pages 338–351. Schloss Dagstuhl, 2010.
[10] M. Carbone, K. Honda, and N. Yoshida. Structured Communication-Centred Programming for Web
Services. In ESOP, volume 4421 of LNCS, pages 2–17. Springer, 2007.
[11] M. Carbone, K. Honda, and N. Yoshida. Structured Interactional Exceptions in Session Types. In Proc.
of CONCUR’08, volume 5201 of LNCS, pages 402–417. Springer, 2008.
[12] M. Carbone, K. Honda, and N. Yoshida. Structured communication-centered programming for web
services. ACM Trans. Program. Lang. Syst., 34(2):8, 2012.
[13] M. Carbone and F. Montesi. Deadlock-Freedom-by-Design: Multiparty Asynchronous Global Programming. In POPL, pages 263–274. ACM, 2013.

52

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

[14] G. Castagna, M. Dezani-Ciancaglini, and L. Padovani. On global types and multi-party session. Logical
Methods in Computer Science, 8(1), 2012.
[15] E. Cooper, S. Lindley, P. Wadler, and J. Yallop. Links: Web Programming Without Tiers. In FMCO,
volume 4709 of LNCS, pages 266–296. Springer, 2006.
[16] M. Coppo, M. Dezani-Ciancaglini, and B. Venneri. Self-adaptive multiparty sessions. Service Oriented
Computing and Applications, 9(3-4):249–268, 2015.
[17] G. Cugola, C. Ghezzi, and L. S. Pinto. DSOL: a declarative approach to self-adaptive service orchestrations. Computing, 94(7):579–617, 2012.
[18] M. Dalla Preda, M. Gabbrielli, S. Giallorenzo, I. Lanese, and J. Mauro. Dynamic choreographies - safe
runtime updates of distributed applications. In COORDINATION, volume 9037 of LNCS, pages 67–82.
Springer, 2015.
[19] M. Dalla Preda, S. Giallorenzo, I. Lanese, J. Mauro, and M. Gabbrielli. AIOCJ: A choreographic
framework for safe adaptive distributed applications. In SLE, volume 8706 of LNCS, pages 161–170.
Springer, 2014.
[20] C. Di Giusto and J. A. Pérez. Disciplined structured communications with consistent runtime adaptation.
In SAC, pages 1913–1918. ACM, 2013.
[21] Eclipse website. http://www.eclipse.org/.
[22] C. Ghezzi, M. Pradella, and G. Salvaneschi. An evaluation of the adaptation capabilities in programming
languages. In SEAMS, pages 50–59. ACM, 2011.
[23] R. Hirschfeld, P. Costanza, and O. Nierstrasz. Context-oriented Programming. Journal of Object
Technology, 7(3):125–151, 2008.
[24] K. Honda, N. Yoshida, and M. Carbone. Multiparty Asynchronous Session Types. In POPL, pages
273–284. ACM, 2008.
[25] H. Hüttel et al. Foundations of session types and behavioural contracts. ACM Computing Surveys, 2016.
[26] Jolie website. http://www.jolie-lang.org/.
[27] I. Jureta, S. Faulkner, and P. Thiran. Dynamic requirements specification for adaptable and open
service-oriented systems. In ICSOC, volume 4749 of LNCS, pages 270–282. Springer, 2007.
[28] J. O. Kephart and D. M. Chess. The vision of autonomic computing. Computer, 36(1):41–50, 2003.
[29] I. Lanese, A. Bucchiarone, and F. Montesi. A Framework for Rule-Based Dynamic Adaptation. In TGC,
volume 6084 of LNCS, pages 284–300. Springer, 2010.
[30] I. Lanese, C. Guidi, F. Montesi, and G. Zavattaro. Bridging the Gap between Interaction- and ProcessOriented Choreographies. In SEFM, pages 323–332. IEEE, 2008.
[31] I. Lanese, F. Montesi, and G. Zavattaro. Amending choreographies. In WWV, volume 123, pages 34–48.
EPTCS, 2013.
[32] L. A. F. Leite et al. A systematic literature review of service choreography adaptation. Service Oriented
Computing and Applications, 7(3):199–216, 2013.
[33] C. Metz. The epic story of dropbox’s exodus from the amazon cloud empire. Wired, http://www.wired.
com/2016/03/epic-story-dropboxs-exodus-amazon-cloud-empire/.
[34] F. Montesi. Kickstarting choreographic programming. In WS-FM, pages 3–10. Springer, 2015.
[35] F. Montesi, C. Guidi, and G. Zavattaro. Composing services with JOLIE. In ECOWS, pages 13–22.
IEEE, 2007.
[36] F. Montesi, C. Guidi, and G. Zavattaro. Service-oriented programming with Jolie. In Web Services
Foundations, pages 81–107. Springer, 2014.
[37] F. Montesi and N. Yoshida. Compositional choreographies. In CONCUR, volume 8052 of LNCS, pages
425–439. Springer, 2013.
[38] I. Neamtiu and M. W. Hicks. Safe and timely updates to multi-threaded programs. In PLDI, pages
13–24. ACM, 2009.
[39] M. Neubauer and P. Thiemann. From sequential programs to multi-tier applications by program
transformation. In POPL, pages 221–232. ACM, 2005.
[40] M. Neubauer and P. Thiemann. Placement inference for a client-server calculus. In ICALP, volume 5126
of LNCS, pages 75–86. Springer, 2008.
[41] P. Nienaltowski. Practical framework for contract-based concurrent object-oriented programming. PhD
thesis, ETH Zurich, 2007.
[42] R. Pawlak et al. JAC: an aspect-based distributed dynamic framework. Software: Practice and Experience,
34(12):1119–1148, 2004.

DYNAMIC CHOREOGRAPHIES

53

[43] S. Rinderle, A. Wombacher, and M. Reichert. Evolution of Process Choreographies in DYCHOR. In
OTM Conferences (1), volume 4275 of LNCS, pages 273–290. Springer, 2006.
[44] Rust website. http://www.rust-lang.org/.
[45] G. Salaün, T. Bultan, and N. Roohi. Realizability of choreographies using process algebra encodings.
IEEE T. Services Computing, 5(3):290–304, 2012.
[46] D. Sangiorgi and D. Walker. The pi-calculus: a Theory of Mobile Processes. Cambridge university press,
2003.
[47] Scribble website. http://www.jboss.org/scribble.
[48] A. Wombacher. Alignment of choreography changes in BPEL processes. In IEEE SCC, pages 1–8. IEEE,
2009.
[49] Xtext website. http://www.eclipse.org/Xtext/.
[50] Z. Yang, B. H. C. Cheng, R. E. K. Stirewalt, J. Sowell, S. M. Sadjadi, and P. K. McKinley. An
aspect-oriented approach to dynamic adaptation. In WOSS, pages 85–92. ACM, 2002.
[51] S. Yegulalp. Mozilla’s Rust-based Servo browser engine inches forward. InfoWorld, http://www.infoworld.
com/article/2905688/applications/mozillas-rust-based-servo-browser-engine-inches-forward.
html.

54

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

Appendix A. Proof of Theorem 6.3
In order to prove the bound on the complexity of the connectedness check we use the lemma
below, showing that the checks to verify the connectedness for a single sequence operator
can be performed in linear time on the size of the sets generated by transI and transF.
Lemma A.1. Given S, S 0 sets of multisets of two elements, checking if ∀ s ∈ S . ∀s0 ∈
S 0 . s ∩ s0 6= ∅ can be done in O(n) steps, where n is the maximum of |S| and |S 0 |.
Proof. Without loss of generality, we can assume that |S| ≤ |S 0 |. If |S| ≤ 9 then the check
can be performed in O(n) by comparing all the elements in S with all the elements in S 0 . If
|S| > 9 then at least 4 distinct elements appear in the multisets in S since the maximum
number of multisets with cardinality 2 obtained by 3 distinct elements is 9. In this case the
following cases cover all the possibilities:
• there exist distinct elements a, b, c, d s.t. {a, b}, {a, c}, and {a, d} belong to S. In this case
for the check to succeed all the multisets in S 0 must contain a, otherwise the intersection
of the multiset not containing a with one among the multisets {a, b}, {a, c}, and {a, d}
is empty. Similarly, since |S 0 | > 9, for the check to succeed all the multisets in S must
contain a. Hence, if {a, b}, {a, c}, and {a, d} belong to S then the check succeeds iff a
belongs to all the multisets in S and in S 0 .
• there exist distinct elements a, b, c, d s.t. {a, b} and {c, d} belong to S. In this case the
check succeeds only if S 0 is a subset of {{a, c}, {a, d}, {b, c}, {b, d}}. Since |S 0 | > 9 the
check can never succeed.
• there exist distinct elements a, b, c s.t. {a, a} and {b, c} belong to S. In this case the
check succeeds only if S 0 is a subset of {{a, b}, {a, c}}. Since |S 0 | > 9 the check can never
succeed.
• there exist distinct elements a, b s.t. {a, a} and {b, b} belong to S. In this case the check
succeeds only if S 0 is a subset of {{a, b}}. Since |S 0 | > 9 the check can never succeed.
Summarising, if |S| > 9 the check can succeed iff all the multisets in S and in S 0 share a
common element. The existence of such an element can be verified in time O(n).
Theorem 6.3 (Connectedness-check complexity).
The connectedness of a DIOC process I can be checked in time O(n2 log(n)), where n is the
number of nodes in the abstract syntax tree of I.
Proof. To check the connectedness of I we first compute the values of the functions transI
and transF for each node of the abstract syntax tree (AST). We then check for each sequence
operator whether connectedness holds.
The functions transI and transF associate to each node a set of pairs of roles. Assuming an
implementation of the data set structure based on balanced trees (with pointers), transI and
transF can be computed in constant time for interactions, assignments, 1, 0, and sequence
constructs. For while and scope constructs computing transF(I 0 ) requires the creation of
balanced trees having an element for every role of I 0 . Since the roles are O(n), transF(I 0 )
can be computed in O(n log(n)). For parallel and if constructs a union of sets is needed. The
union costs O(n log(n)) since each set generated by transI and transF contains at maximum
n elements.
Since the AST contains n nodes, the computation of the sets generated by transI and
transF can be performed in O(n2 log(n)).
To check connectedness we have to verify that for each node I 0 ; I 00 of the AST ∀R1 →
R2 ∈ transF(I 0 ), ∀S1 → S2 ∈ transI(I 00 ) . {R1 , R2 } ∩ {S1 , S2 } 6= ∅. Since transF(I 0 ) and

DYNAMIC CHOREOGRAPHIES

55

transI(I 00 ) have O(n) elements, thanks to Lemma A.1, checking if I 0 ; I 00 is connected costs
O(n). Since in the AST there are less than n sequence operators, checking the connectedness
on the whole AST costs O(n2 ).
The complexity of checking the connectedness of the entire AST is therefore limited by
the cost of computing functions transI and transF and of checking the connectedness. All
these activities have a complexity of O(n2 log(n)).

Appendix B. Proofs of Section 7.1
Lemma 7.9 (Distinctness of Global Indexes). Given a well-annotated DIOC I, a global
η1
ηn
state Σ, and a set of updates I, if hΣ, I, Ii −→ . . . −→ hΣ0 , I0 , I 0 i then all global indexes in I 0
are distinct.
Proof. The proof is by induction on the number n of transitions, using a stronger inductive
hypothesis: indexes are distinct but, possibly, inside DIOC subterms of the form I; i :
while b@R {I 0 }. In this last case, the same index can occur both in I and in I 0 , attached
to constructs with different global indexes. The statement of the Lemma follows directly:
first, distinct indexes imply distinct global indexes; second, global indexes of I and of I 0 are
distinct, since I 0 is inside the while loop whilst I is not.
In the base case (n = 0), thanks to well annotatedness, indexes are
√ always distinct. The
inductive case follows directly by induction for transitions with label . Otherwise, we √
have
a case analysis on the only axiom which derives a transition with label different from .
The only difficult cases are bDIOC |While-unfold e and bDIOC |Up e.
In the case of Rule bDIOC |While-unfold e, note that the while is enabled, hence it cannot
be part of a term of the form I; i: while b@R {I 0 }. Hence, indexes of the body of the while
loop do not occur elsewhere. As a consequence, after the transition no clashes are possible
with indexes in the context. Note also that indexes of the body of the loop are duplicated,
but the resulting term has the form I; i: while b@R {I 0 }, thus global indexes are distinct
by construction.
The case bDIOC |Up e follows thanks to the condition freshIndexes(I 0 ).
Lemma 7.15. Given a well-annotated connected DIOC process I and for each state Σ the
DPOC network proj(I, Σ) is such that:
(1) events(I) ⊆ events(proj(I, Σ));
(2) ∀ ε1 , ε2 ∈ events(I).ε1 ≤DIOC ε2 ⇒ ε1 ≤DP OC ε2 ∨ ε1 ≤DP OC ε2
Proof.
(1) By definition of projection.
(2) Let ε1 ≤DIOC ε2 . We have a case analysis on the condition used to derive the dependency.
Sequentiality: Consider I = I 0 ; I 00 . If events are in the same role the implication
follows from the sequentiality of the ≤DP OC .
Let us show that there exists an event ε00 in an initial interaction of I 00 such that either
ε00 ≤DP OC ε2 or ε00 ≤DP OC ε2 . The proof is by induction on the structure of I 00 . The
only difficult case is sequential composition. Assume I 00 = I1 ; I2 . If ε2 ∈ events(I1 )
the thesis follows from inductive hypothesis. If ε2 ∈ events(I2 ) then by induction
there exists an event ε3 in an initial interaction of I2 such that ε3 ≤DP OC ε2 or
ε3 ≤DP OC ε2 . By synchronisation (Definition 7.14) we have that ε3 ≤DP OC ε2 or
ε3 ≤DP OC ε2 . By connectedness we have that ε3 or ε3 are in the same role of an

56

M. DALLA PREDA, M. GABBRIELLI, S. GIALLORENZO, I. LANESE, AND J. MAURO

event ε4 in I 0 . By sequentiality (Definition 7.14) we have that ε4 ≤DP OC ε3 or
ε4 ≤DP OC ε3 . By synchronisation we have that ε4 ≤DP OC ε3 or ε4 ≤DP OC ε3 . The
thesis follows from the inductive hypothesis on ε4 and by transitivity of ≤DP OC .
Let us also show that there exists a final event ε000 ∈ events(I 0 ) such that ε1 ≤DP OC ε000
or ε1 ≤DP OC ε000 . The proof is by induction on the structure of I 0 . The only difficult
case is sequential composition. Assume I 0 = I1 ; I2 . If ε1 ∈ events(I2 ) the thesis
follows from inductive hypothesis. If ε1 ∈ events(I1 ) then the proof is similar to the
one above, finding a final event in I1 and applying sequentiality, synchronisation,
and transitivity.
The thesis follows from the two results above again by sequentiality, synchronisation,
and transitivity.
Scope: it means that either (a) ε1 =↑ξ and ε2 is an event in the scope or (b) ε1 =↑ξ and
ε2 =↓ξ , or (c) ε1 is an event in the scope and ε2 =↓ξ . We consider case (a) since case
(c) is analogous and case (b) follows by transitivity. If ε2 is in the coordinator then
the thesis follows easily. Otherwise it follows thanks to the auxiliary synchronisations
with a reasoning similar to the one for sequentiality.
Synchronisation: it means that ε1 is a sending event and ε2 is the corresponding
receiving event, namely ε1 = ε2 . Thus, since ε2 ≤DP OC ε2 then ε2 ≤DP OC ε2 .
If: it means that ε1 is the evaluation of the guard and ε2 is an event in one of the two
branches. Thus, if ε2 is in the coordinator then the thesis follows easily. Otherwise it
follows thanks to the auxiliary synchronisations with a reasoning similar to the one
for sequentiality.
While: it means that ε1 is the evaluation of the guard and ε2 is in the body of the
while loop. Thus, if ε2 is in the coordinator then the thesis follows easily. Otherwise
it follows thanks to the auxiliary synchronisations with a reasoning similar to the
one for sequentiality.
Lemma 7.20. Let I be a well-annotated connected DIOC process and Σ a state. Then the
projection N = proj(I, Σ) is a well-annotated DPOC network with respect to ≤DP OC .
Proof. We have to prove that proj(I, Σ) satisfies the conditions of Definition 7.17 of wellannotated DPOC:
C1: For each global index ξ there are at most two communication events on programmerspecified operations with global index ξ and, in this case, they are matching events.
The condition follows by the definition of the projection function, observing that in
well-annotated DIOCs, each interaction has its own index, and different indexes are
mapped to different global indexes.
C2: Only events which are minimal according to ≤DP OC may correspond to enabled
transitions. This condition follows from Lemma 7.19.
C3: For each pair of non-conflicting sending events [fξ ]R and [fξ0 ]R on the same operation
o? and with the same target R0 such that ξ =
6 ξ 0 we have [fξ ]R ≤DP OC [fξ0 ]R or
[fξ0 ]R ≤DP OC [fξ ]R . Note that the two events are in the same role R, thus without loss of
generality we can assume that there exist two processes P, P 0 such that [fξ ]R ∈ events(P )
and [fξ0 ]R ∈ events(P 0 ) and there is a subprocess of N of one of the following forms:
• P ; P 0 : the thesis follows by sequentiality (Definition 7.14);
• P |P 0 : this case can never happen for the reasons below. For events on programmerspecified operations this follow by the definition of projection, since the prefixes of
the names of operations are different. For events on auxiliary operations originated

DYNAMIC CHOREOGRAPHIES

57

by the same construct this follows since all the targets are different. For events on
auxiliary operations originated by different constructs this follows since the prefixes of
the names of the operations are different.
• if b {P } else {P 0 }: this case can never happen since the events are non-conflicting
(Definition 7.16).
C4: Similar to the previous case, with receiving events instead of sending events.
C5: If ε is an event inside a scope with global index ξ then its matching events ε (if they
exist) are inside a scope with the same global index. This case holds by definition of the
projection function.
C6: If two events have the same index but different global indexes then one of them, let us
call it ε1 , is inside the body of a while loop with global index ξ1 and the other, ε2 , is not.
Furthermore, ε2 ≤DP OC εξ1 where εξ1 is the guarding while-event of the while loop with
global index ξ1 . By definition of well-annotated DIOC and of projection the only case
where there are two events with the same index but different global indexes is for the
auxiliary communications in the projection of the while construct, where the conditions
hold by construction.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a letter
to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany

