Coordinating first-order multiparty interactions.
A first-order multiparty interaction is an abstraction mechanism that defines communication among a set of formal process roles. Actual processes participate in a first-order interaction by enroling into roles, and execution of the interaction can proceed when all roles are filled by distinct processes. As in CSP, enrolement statements can serve as guards in alternative commands. The enrolement guard-scheduling problem then is to enable the execution of first-order interactions through the judicious scheduling of roles to processes that are currently ready to execute enrolement guards. We present a fully distributed and message-efficient algorithm for the enrolement guard-scheduling problem, the first such  solution of which we are aware. We also describe several extensions of the algorithm, including: generic roles; dynamically changing environments, where processes can be created and destroyed at run time; and nested-enrolement, which allows interactions to be nested.
Introduction
A multiparty interaction is a set of I/O actions executed
jointly by a number of processes, each of
which must be ready to execute its own action
for any of the actions in the set to occur. An
attempt to participate in an interaction delays a
process until all other participants are available.
After the actions are executed, the participating
processes continue their local computation, usually
asynchronously. Languages like CSP and Ada support
interaction only between two processes. How-
ever, for many applications a higher level of abstraction
can be obtained by permitting interaction
among an arbitrary number of processes. For
example, consider the well-known dining philosophers
problem. The natural unit of process inter-action
in this setting is between a philosopher and
its two neighboring forks; i.e., a multiparty synchronization
involving three processes.
It is useful to distinguish between zeroth-order
multiparty interactions where the participants are
fixed in advance, and first-order multiparty interactions
where the participants may vary dynami-
cally. For example, a zeroth-order multicast inter-action
in which process P sends a message m to Q
and R is captured by the code:
Research supported by the National Science Foundation
under Grant CCR-8704309.R :: B[y := m]
The notation we use is based on IP [7, 8]: B is
the interaction name and m, x, and y are variables
local to P , Q, and R, respectively. An interaction
describes the action taken by a process
engaged in the interaction; e.g., x := m means that
assigns x the non-local value of m. Many of the
existing constructs for multiparty interaction are
zeroth-order, including shared actions [16], joint
actions [1], interactions in Raddle [4], interactions
in IP , and interaction types [13].
A first-order multiparty interaction is an abstraction
mechanism that defines activities among
a set of roles, which serve as formal process param-
eters. Actual processes participate in an interaction
by enroling 1 into the roles. We first consider
partners-unnamed enrolement [9] where a process
is not permitted to name any other potential participants
for the interaction in question. In this
scheme, an instance of the interaction is activated
when all roles are filled by distinct processes; the
enrolers then communicate in the manner as described
by the interaction. The notion of Script [9]
and the team construct of Raddle and IP all support
first-order multiparty interactions.
Consider once again the multicast example. We
can define a first-order interaction having three
roles, a transmitter and two recipients, as follows:
first-order interaction 2-cast ::
role recipient 1
role recipient 2
(y: out) :: y := z
N. Francez and I. R. Forman suggest the new word en-
role to mean "to enter a role."
can execute the following en-
rolement statements to activate an instance of the
first-order interaction:
transmitter(m)@2-cast
(x)@2-cast
R :: enrole recipient 2
(y)@2-cast
Any other three processes can reuse this 2-cast
interaction to communicate, and thus a decision
must be made whether to allow concurrent activations
of the same first-order interaction. In Rad-
dle and Script, first-order interactions are reentrant
thereby permitting concurrent activations, while in
IP, this decision is currently left unspecified. In
this paper, we also view first-order interactions as
reentrant: the potential concurrency can lead to
increased performance, and, as pointed out by N.
Francez [5], the absence of any sequentialization of
activations leaves the interaction itself as the sole
source of process synchronization. However, as also
pointed out in [5], the accompanying proof system
may become more complex in light of concurrent
activations.
As in CSP, multiparty interactions-both zeroth-order
and first-order-can serve as guards in alternative
and repetitive commands. In the zeroth-order
case, an interaction statement appearing as
a guard can be executed only if all the other participants
are in agreement. For example, consider
the following program:
R
can execute a[ ] if and when Q and R agree to execute
their own a[ ] actions. The guard-scheduling
problem for zeroth-order interactions has been elegantly
characterized by Chandy and Misra as one
of committee coordination [3]: each professor in a
university serves on one or more committees, the
members of which are fixed; furthermore, a committee
cannot convene until all its members are
present (as such, no two committees with a common
member can convene simultaneously).
For the first-order case, an enrolement statement
appearing as a guard in a process P can be
executed only if a set of processes, including P it-
self, agree to fill all roles of the targeted interaction. 2
To illustrate, consider the following program:
R
U
S and T are first-order interactions having roles
respectively. P can execute en-
role s 1
@S if and when two other processes agree
to enrole into s 2
and s 3
The following issues are peculiar to the implementation
of first-order guards:
ffl Since the participants of a first-order inter-action
vary dynamically, determining which
set of processes together can enrole in an
instance of the interaction is more complex
than in the zeroth-order case. In fact, we
show that it is closely related to the maximum
matching problem [11].
ffl Instances of a first-order interaction can be
concurrently activated.
ffl As more than one process can enrole into
the same role, the failure of any one of them
should not preclude the others from filling
the role. Thus, first-order interactions are
inherently fault-tolerant.
The distributed algorithms of [17, 3, 2, 13, 15]
for multiparty interaction guard scheduling are zeroth-order
in nature. The algorithms of [3, 2, 15] employ
a fixed coordinator for each interaction and
In IP the situation is somewhat different. IP's team is
an abstraction mechanism for multiparty interactions, the
zeroth-order construct of IP. Enrolement into a team does
not delay a process, but rather the multiparty interactions
to be executed first within the role [6].
thus cannot realize concurrent activations of a first-order
interaction, nor can they tolerate the failure
of the coordinator. The algorithms of [17, 13] employ
mutual coordination among the participants,
but are highly dependent on the fact that the participants
of each interaction are fixed. Therefore,
there is no straightforward way to adapt these algorithms
to a first-order setting.
Summary of Technical Results
The main contribution of this paper (Section 3) is
a distributed algorithm for the enrolement guard
scheduling problem, the first first-order solution of
which we are aware. The algorithm admits the
possibility for any process, upon reaching an alternative
command, to behave as the coordinator of
a first-order interaction. Thus, unlike the zeroth-order
algorithms, it permits concurrent activations:
each activation will have its own coordinator. It is
also fault-tolerant as the coordinator is not designated
in advance. Moreover, the algorithm has
low message complexity: at most 6m messages per
process, per interaction guard, where m is number
of processes that can potentially enrole into the
interaction.
In the above algorithm, a bi-partite graph data
structure is used to associate processes with their
potential roles, and the coordinator is required to
perform maximum matching on this graph to decide
which processes to schedule. The best-known
bound for this problem is currently O(n 2:5 ) time,
where n is the number of nodes in the graph [11].
In Section 5, we show that in a setting in which
a process can target at most one role of an inter-action
at any one time, maximum matching can
be safely avoided and, instead, a coordinator can
decide which processes to schedule in linear time.
Moreover, through the use of generic roles, we argue
that this restriction on alternative commands
is quite palatable in practice.
In Section 6, we then consider partners-named
enrolement , where an enroler can name some or all
of the other participants in a first-order interaction.
This type of enrolement was initially presented in
the context of Script [9]. We show that, in gen-
eral, enrolement guard scheduling in this setting
is NP-complete, even when enrolement statements
cannot act as guards. However, partners-named
enrolement is desirable in some applications. For
example, a process P may at times desire to multicast
to a particular group G of recipients. To
ensure that the message is received only by processes
in G, P names exactly these processes as
the recipients. We present two restricted naming
conventions, which seem reasonable in practice, for
which the problem can be solved efficiently.
Finally, in Section 7, we extend our algorithm
to work in a dynamically changing environment
where processes may be created and destroyed at
run time, a problem suggested in [9, 6].
Simple Model of First-Order
Multiparty Interactions
We consider a distributed system to be a set of concurrent
processes that interact by engaging in first-order
multiparty interactions. Each interaction 3 I
has a fixed set R(I) of roles into which processes
can enrole. For each role r 2 R(I) there is a fixed
set P(r) of processes that can potentially enrole
into role r. Further, we let
i.e., the set of processes that can potentially enrole
into some role of I. We assume that R(I) and each
P(r) are finite and known to every process in P(I).
From time to time, a process enters its enrole-
ment phase, where it is ready to enrole into any
single role from a set of potential roles, possibly
from different interactions. We define a quorum of
I to be a set
to enrole into I as r i g
Additionally, the pairs of a quorum are required to
be component-wise mutually distinct. These p i 's
together can leave their enrolement phase and activate
an instance of I with p i filling role r i .
The first-order guard scheduling problem then
is to establish quorums involving mutually disjoint
sets of processes from the processes currently in
their enrollment phases.
3 In the sequel, unless stated otherwise, by interaction we
mean of the first-order type.
3 Description of the Algorithm
We assume an underlying network of processes that
is completely connected via reliable, FIFO communication
channels, and that processes communicate
exclusively by message passing. Furthermore, messages
are timestamped; processes use the timestamps
to maintain their logical clocks [14].
3.1

Overview

When a process p i enters its enrolement phase, it
chooses an interaction I in which it is ready to
enrole, and then attempts to establish a quorum
of I. p i builds its quorum incrementally. Initially,
the partial quorum of I is
is ready to assume role r of I g
called the coordinator of the partial quorum.
tries to capture processes to fill all the roles
of I. For each role r, p i chooses a process p j in
P(r) and sends it a capture request . If p j is ready
to assume any role r of I, and is willing to be
captured by p i , request and
provides p i with the set R j of roles of I that p j
is ready to assume. p i then adds the pairs (p
such that r 2 R j to its partial quorum. However,
request because it is not ready to
assume a role of I or because it does not wish to be
captured by p i , then p i must find another process
for role r.
succeed when its partial quorum contains
a quorum. It then directs each process of the
quorum to assume its role in the quorum, and releases
any additional processes it may have cap-
tured. However, if p i determines that there is a
role of I for which it cannot capture a process, it
aborts the attempt and releases all members of its
partial quorum. If p i has another interaction I 0 in
which it is ready to enrole, it attempts to build
a quorum of I 0 ; otherwise, it enters an idle state
waiting to be captured.
To reduce the message complexity of the algo-
rithm, we allow a coordinator to only capture older
processes. Here we measure the age of a process by
the unique entry time obtained from the contents
of the process's logical clock when it entered its
current enrolement phase. 4 The larger the entry
time a process possesses, the younger the process
is. Allowing a coordinator to only capture older
processes means that only the youngest process in
a quorum can assemble the quorum, and prevents
the other processes from wasting too many messages
in an attempt to build the quorum only to
learn that a younger process is not yet ready.
To ensure coordinators establish quorums that
involve mutually disjoint sets of processes, a process
can be captured by only one coordinator at
a time. Obviously, the requirements of different
coordinators may conflict. These conflicts are re-solved
using the unique entry times obtained by
each coordinator. (The same technique has also
proven useful in implementing dynamically structured
multiparty interactions [12].)
A conflict arises when a coordinator attempts
to capture a process that already belongs to another
coordinator. Conflicts are resolved in favor
of older coordinators in order to prevent a coordinator
from being locked out from capturing pro-
cesses. That is, we let the older of the two co-ordinators
capture/retain the process, say p, under
contention. The younger coordinator has then
to find an alternative process for the same role as
played by p; or wait hoping that p will eventually
be released by the older coordinator either because
the older coordinator could not build a quorum or
because it decided on a quorum which excluded p.
When a coordinator p i is waiting for a captured
process p j to be released by an older coordinator
we say that capture request has been deferred
by both maintain this "wait-
ing for" relation until either one of the following
occurs:
finishes (succeeds or aborts) its coordination
and withdraws its capture request to p j .
successfully builds a quorum involving
cannot build a
quorum involving p j . So p j now grants p i 's
capture request.
4 Entry times can be made unique by additionally considering
process ids.
We show in Section 4 that our algorithm guarantees
that any quorum contained in the partial
quorum of p i involves p i itself. This prevents p i
from coordinating one quorum after another from
a given enrolement phase, assuming that p i is old
enough to win most contentions. Allowing p i to
coordinate too many quorums could severely limit
the system's concurrency. In fact we can show that
if for a given enrolement phase there exists at least
k quorums that involve mutually disjoint sets of
processes, then at least k coordinators will establish
quorums that involve mutually disjoint sets of
processes.
3.2 The Algorithm
Each process p i executes concurrently two compo-
nents, coord i and slave i . We use coord i to realize
the behavior of p i when p i acts as a coordinator
of a partial quorum as described earlier, and slave i
for behavior in reacting to capture requests.
In our algorithm, coordinators communicate exclusively
with slaves, and vice versa.
Recall that a coordinator p i starts out with a
partial quorum involving itself; that is, slave i is
initially captured by coord i . Our strategy for re-solving
conflicts guarantees that slave i will remain
captured by coord i until coord i has established a
quorum or has entered its idle state due to its inability
to build any quorum. This is because when
a coord j attempts to capture slave i , if p j is older
than not allowed to capture slave i .
However, if p j is younger, then coord i wins the contention
and retains slave i . Therefore, it will never
be the case that the two components get out-of-
synch, e.g., coord i is still busy in building a quorum
while slave i has already advanced to the next
enrolement phase.
Coord i proceeds as follows:
coord i maintains the following variables:
the current partial quorum. It contains pairs
r) such that p j is ready to assume role r
and slave j is captured by coord i .
D: set of pairs (p r) such that p j is ready to assume
role r but slave j has deferred a capture
request by coord i .
R: the set of slaves coord i has requested for capture

coord i starts its quorum-building activity when
process p i enters its enrolement phase. It begins
by selecting an interaction I in which process p i is
ready to enrole, and sets is ready to assume role r of I g,
g. coord i then executes the
following procedure to build a quorum of I. If suc-
cessful, i.e., P contains a quorum Q, then coord i
sends Success(I; r j ) to slave j for each (p
directing p j to enrole in I as role r j . coord i also
releases any additional slaves it may have captured
by sending each slave of Release message,
and withdraws the capture request it made to each
slave of D by sending it a Withdrawal message. If
coord i fails to establish a quorum of I, it releases
every captured slave except slave i and withdraws
the capture request it made to each slave of D.
If coord i has another yet-to-be-tried interaction I 0 ,
it continues by attempting to build a quorum of
I
building activity, and then becomes idle.
The procedure to build a quorum of I is as follows

contains a quorum Q (which must involve
versely, coord i fails to build a quorum if ei-
ther: there exists a role r such that every
slave of P(r) when requested by coord i was
not ready to assume role or every slave
of P(I) is either captured by coord i or has
rejected capture by coord i , and P does not
contain any quorum.
ffl If coord i has not yet succeeded nor failed,
then it can proceed conservatively-by waiting
for the slave of a process in D to grant or
reject its deferred capture request, or aggressively-
by sending a new capture request to the slave
of a process p not in R, hoping that p is ready
to fill a role of I that would assist coord i to
reach a quorum. The choice constitutes a
fine tuning of the algorithm: the conservative
approach may result in fewer messages,
while the aggressive approach may give better
response time.
- When a slave j of D grants coord i 's deferred
request, coord i moves all pairs of
the form (p r) from D to P . If slave j
rejects coord i 's deferred request, coord i
deletes all such pairs from D.
- If coord i wishes to capture another slave k ,
it adds p k to R, sends Request(t i ; I) to
slave k , and then waits for a response
from slave k . Here t i is the entry time
of p i . If the response is
coord i adds (p k ; r) to P for each r 2
R I ; if the response is Deferred (R I ), it
adds the (p k ; r)'s to D; otherwise it does
nothing.
- Meanwhile, if coord i receives a Switch
message from a captured slave j , asking
it to release slave j because a coordinator
older than coord i wishes to capture
slave j , then coord i replies Switch ok to
the request and moves all pairs of the
from P to D.
Slave i proceeds as follows:
slave i maintains a priority queue of triples (p
such that slave i has deferred the capture request
. The highest priority is
given to the triple with the smallest timestamp.
slave i waits for its captor, coord k , if any, to establish
a quorum. (slave i is initially captured by
coord i when coord i starts its quorum-building ac-
tivity.) If slave i receives Success(I; r i ) from coord k ,
it sends for each triple (p
in the queue; i.e., all deferred requests are now re-
jected. slave i then enroles into I as role r i . How-
ever, if coord k sends a Release message to slave i
without placing p i in a quorum, slave i deletes from
the queue the triple (p that has the smallest
I 0 is the
set of roles p i can assume in interaction I 0 . That
is, slave i grants the oldest of its deferred capture
requests, which is consistent with our strategy for
resolving conflicts. If the queue is empty, slave i
idles, waiting to be captured.
slave i may also receive Request(t j ; I 0 ) from a
coordinator coord j . If p i is not ready to enrole
in I 0 or p i is younger than p j , then slave i rejects
coord j 's request. Otherwise, there are two cases.
slave i is not captured by any coordinator: it
grants coord j 's request. (2) slave i is captured by
some coord k : if p k is older than p j , then slave i remains
captured by coord k , inserts triple (p
into its priority queue, and sends Deferred (R I 0 )
to coord j , where R I 0 is the set of roles p i can assume
in interaction I 0 . Else, slave i sends Switch to
coord k asking it to release slave i . After receiving
the confirmation Switch ok , slave i grants coord j 's
request, and inserts the triple (p into the
queue thereby now deferring coord k 's capture request
Also, when slave i receives Withdrawal from some
coord l , it simply deletes coord l 's capture request
from the queue.
The algorithms for coord i and slave i are given
in

Figures

1 and 2, respectively. Together they
constitute our algorithm for the first-order guard
scheduling problem. Each algorithm is presented
as a CSP-like repetitive construct, and each guarded
command is numbered for ease of reference. We
assume weak-fairness, i.e., every command whose
guard is continuously enabled is eventually exe-
cuted. Note that the coordinator and slave of a
process p i are logically separate: the guarded commands
of both components can be combined into
a single repetitive construct.
In

Figures

1 and 2, the entry time of process
with respect to its current enrolement phase, is
given by variable t i . Also, the variable G i represents
the set of roles that p i is ready to assume,
contains pairs (I; R I ) such that p i is ready
to assume the set R I of roles of I. G i is updated
by its enrolement phase, and
is reset to ; when p i leaves this phase.
3.3 An Example
To illustrate our algorithm's behavior, consider an
interaction I with three roles r 1
, and r 3
. Assume
that
and
are ready for role r 1
and
for r 2
, and p 5
for r 3
. Furthermore, the
entry times of the six processes are in increasing or-
is the youngest. In the following we give
a possible scenario of events for the six processes
1.1 active aborted
for
do
send Release to slave j
for do
send Withdrawal to slave j
tried
send Release to slave
active := false;
I := I
1.2 active
target := recruit
send
R
1.3 active
contains a quorum Q \Gamma!
for (p
send
) to slave j
for
do
send Release to slave j
for do
send Withdrawal to slave j
active := false;
1.4 receive Yes(t; R I 0
) from slave j
\Gamma!
for r 2 R I do
for r 2 R I do P
target
else \Gamma! skip
receive No(t; I 0 ) from slave j
\Gamma!
for do
target
else \Gamma! skip
1.6 receive Switch from slave j
\Gamma!
does not contain any quorum;
send Switch ok to slave j
for do
else \Gamma! skip
1.7 receive Deferred (R I ) from slave j \Gamma!
for r 2 R I
do D := D [ f (p
target
the current partial quorum.
D: a set of pairs (p r) such that p j is ready to assume
role r but slave j has deferred a capture request
by coord i
R: the set of slaves p i
has requested for capture.
active : a flag that is true iff coord i is coordinating a
quorum of an interaction.
I: when active , I denotes the interaction for which
coord i is coordinating.
target : the slave to which coord i has sent a capture request
but has not yet received any response.
tried (I): a flag that is true iff coord i has tried to establish
a quorum of I .
aborted returns true iff the attempt to build
a quorum of I has failed, i.e., either 9r 2
P does not contain any quorum of I . Initially,
aborted (;; ;; true so that command 1.1 will
be applied.
recruit returns the slave of a process p j ,
that coord i can now attempt to capture,
or returns nil otherwise. For fewer messages, it
can return nil whenever D 6= ;; or, for better
response time, it can return the slave of a process
there is a role r
such that coord i
needs some process to assume
r.

Figure

1: Algorithm for coord i
2.1 receive Success(I ; r) from coord j
\Gamma!
for (p do
send
queue
enrole into I as role
2.2 receive Release from coord j
\Gamma!
captured := false ;
2.3 receive Request(t
\Gamma!
queue
captured \Gamma!
let captor= (p
\Gamma!
reply reply
send Switch to coord k
swflag := true
\Gamma!
send Deferred to coord j
captured \Gamma!
reply reply
else \Gamma! send
2.4 receive Switch ok from coord j \Gamma!
queue
captured := false ;
2.5 receive Withdrawal from coord j \Gamma!
captor \Gamma! captured := false ;
queue
reply \Gamma! reply := reply
else \Gamma! skip
delete (p j
; I) from queue ;
send
) to coord j
captor := (p j
reply \Gamma! reply := reply
for reply do
let
send Deferred
reply
swflag := false
captured : a flag that is true iff slave i is captured. slave i
sets captured to true upon entering the enrole-
ment phase.
swflag : a flag that is true iff slave i has already sent a
Switch to its current captor because some coordinator
older than slave i
's captor wishes to capture
slave i
captor : a triple (p I) such that slave i
is captured by
, which has entry time t j
and is coordinating
interaction I . slave i
sets captor := (p
upon entering the enrolement phase.
queue: a priority queue of triples (p
the capture request Request(t
is
deferred by slave i
. The highest priority is given
to the triple which has the smallest (oldest) t j
a delete operation then returns that triple.
reply : the set of coordinators to which slave i
has not
yet replied to their capture requests.

Figure

2: Algorithm for slave i
executing the algorithm:
requests capture of slave 3
but is re-
jected. It then issues a request to slave 4
but
again is rejected because p 1
is older than both
of p 3
and p 4
. coord 1
then releases slave 1
and
idles.
ffl Similarly, coord 2
and coord 3
release their companion
slaves and become idle after each being
rejected by both slave 5
and slave 6
captures slave 1
and coord 6
both request capture of
slave 4
which belongs to coord 4
. Their requests
are deferred by slave 4
as
are younger than p 4
's requests to capture slave 5
and slave 6
are rejected. It releases slave 1
and slave 4
and
then idles.
slave 4 grants coord 5 's capture request.
captures slave 1
requests capture of slave 1
. Since p 5
is older than p 6
captures slave 1
and
coord 6
's capture request is deferred by slave 1
coord 5
then has established a quorum involving
and p 5
ffl After capturing slave 2 and slave 3 , coord 6 then
has established another quorum of I.
4 Analysis of the Algorithm
In this section we prove that our algorithm satisfies
the requisite safety and liveness properties, and
analyze its message complexity.
Theorem 1 (Safety) At any time a process can
participate in at most one established quorum.
Proof: This is a consequence of the fact that a
coordinator can establish a quorum only if it captures
all of the processes involved in the quorum,
and that a process can be captured by only one
coordinator at a time.
request cannot be deferred
forever nor infinitely often.
Proof: A capture request issued by a coordinator
i to a slave p j may be granted, rejected, or deferred
by p j . However, a capture request that is
granted may later need to be deferred in order to
resolve a conflict.
were to defer p i 's capture request forever
or infinitely often, then there must exist a p k older
than p i such that p j remains captured by p k for-
ever, or p k continually recaptures p j infinitely of-
ten. However, p k must stay in the same enrole-
ment phase each time it recaptures will be
younger than p i when p k obtains a new entry time.
Therefore, some slave would also have deferred p k 's
capture request forever or infinitely often. This
would imply the existence of an infinite sequence
of coordinators with strictly increasing ages. Con-
tradiction. 2
Theorem 2 (Liveness) Whenever there exists a
quorum, then, within a finite amount of time, some
process in the quorum will enrole in some interaction

Proof (sketch): Suppose there exists a quorum
Q of an interaction I and let p m be the youngest
process in Q. Then, either (1) a process in Q participates
in some other established quorum, or (2)
eventually establish Q since, no process in
Q can reject p m , and by Lemma 1, eventually all
processes in Q will be captured by p m . In either
case the theorem has been proven. 2
established by a process
must involve p m itself. In fact, p m is the youngest
process in the quorum.
Proof: A process p m cannot be captured by a different
process unless p m has entered its idle state
due to its inability to build any quorum. So, if
there exists a quorum Q of an interaction I in
which p m is the youngest process, then no other
process can capture p m until p m has attempted to
build a quorum of I. By the proof of Theorem 2,
succeed in establishing Q, unless some process
in Q has participated in some other established
quorum. 2
To analyze the algorithm's message complexity,
we define #(p i [I]) to be the number of messages
transmitted by p i itself or generated by other processes
in response to p i 's messages while p i is co-ordinating
I. We consider a worst-case scenario.
1. coord i sends a Request message to slave j .
2. slave j is captured by coord k which is younger
than coord i . So, slave j sends a Switch message
to coord k .
3. coord k sends the confirmation Switch ok to
slave j . coord k 's capture request is now deferred
by slave j .
4. slave j sends a Yes message to coord i .
5. coord i establishes a quorum involving p j . It
sends a Success message to slave j .
6. After p j is placed into a quorum, slave j sends
No to coord k , rejecting coord k 's deferred capture
request.
In a somewhat different scenario in which coord i
fails to place p j into a quorum and thus sends
a Release to slave j , slave j would send coord k a
Yes message to grant its deferred capture request.
Therefore, in its attempt to capture slave j , coord i
generates at most 6 messages.
Theorem 3 Let #(p i [I]) be the number of messages
transmitted by p i itself or generated by other
processes in response to p i 's messages while p i is
coordinating I. Then, #(p i [I])  6 j P(I) j
5 Maximum Matching and Symmetric
Roles
The activation of an instance of an interaction requires
that each role is filled by a distinct process.
However, a process in its enrollment phase may be
ready for different roles of the same interaction.
Let P be the partial quorum of a coordinator p i .
To decide whether P contains a quorum, p i needs
to find in P a subset Q of size jR(I)j such that no
two elements in Q specify the same role or process.
This is just an instance of the maximum matching
problem, and thus can be solved in O(m 2:5 )
time here m is the number of processes captured
by the coordinator p i .
Clearly, we can avoid performing maximum matching
and, therefore reduce the time complexity to
linear, if we do not allow a process to be ready
for more than one role of the same interaction. In
fact, in many multiparty applications certain roles
of an interaction are symmetric in the sense that
a process can enrole into any one of them without
observing any difference. A process tries all
of the symmetric roles because it is unaware of
which of them are being targeted by other processes
and wants to avoid being locked out. For
example, the recipient roles of the first-order multicast
interaction (Section 1) are symmetric. Dead-lock
could arise if two processes were both to specify
unwittingly only role recipient 1
even though
role recipient 2
would equally suffice. To avoid this
dilemma, a process attempting to participate as a
recipient would, somewhat unnaturally, target all
recipient roles.
To facilitate a more pleasant form of enrole-
ment, symmetric roles can be replaced by a single
generic role with a constant indicating the number
of instances of the role to be filled. A process
can then target this generic role without concern
as to which instance it will actually fill. The constant
could even be parameterized and supplied at
run time by another enroler. Considering again
our multicast example, we can define a first-order
interaction with a transmitter and a generic recipient
role which can be filled by m processes; the
transmitter would supply the actual value of m.
Therefore, instances of the interaction can be activated
with somewhat different role structures.
Within the setting of generic roles, we can reasonably
restrict a process to be ready for at most
one role of an interaction at a time without raising
the risk of deadlock.
6 Partners-Named Enrolement
In partners-named enrolement a process can name
some or all of the other enrolers [9]. For a set of
processes to activate an interaction, their naming
specifications must be consistent in the sense that
to fill role r k , then p j indeed enroles
into r k . Note that the naming does not need to
be bilateral. Unfortunately, the guard scheduling
problem becomes intractable, even when a process
can be ready for only one interaction in the enrole-
ment phase (i.e., enrolement statements cannot act
as guards).
Theorem 4 Given a set of partners-named en-
rolement statements each specified by a distinct pro-
cess, the problem of deciding whether there is a
subset consistent in naming their partners is NP-complete

Proof: By reduction from Monotone One-In-Three
As discussed in the introduction, partners-named
enrolement is desirable in some applications. In the
following we present two less severe forms of this
scheme that have efficient implementations, even
when enrolement statements can serve as guards.
First we define the communication graph of an interaction
I to be the undirected graph having node
set R(I) and edges (r
directly communicate.
Partners-fully-named enrolement: A process,
if it wants to name its partners, names all of them.
Direct-partners-named enrolement: A process
names the processes with which it communicates
directly. Moreover, the set of enrolement
guards of an alternative command must satisfy the
disjointedness condition: no two guards that target
the same role name a common partner.
The first restriction is simpler to formulate, but
the second may be more useful in practice. For
example, in a multicast, it is reasonable that the
transmitter names the recipients, but the recipients
should only be required to name the transmitter
and not fellow recipients.
The disjointedness condition of the second form
is crucial in allowing enrolement statements to serve
as guards. Otherwise, one can show that the guard
scheduling problem is still intractable.
Regarding the two restricted forms of partners-
named enrolement, finding a set of enrolement statements
consistent in naming specifications can be
done in linear time, assuming that an interaction's
communication graph is connected. The algorithm
presented in Section 3 can be easily extended to
implement the two forms.
7 Dynamically Changing Environment

Our algorithm can also be extended to a dynamically
changing environment where processes are
created and destroyed at run time. We assume a
model in which, at any time, processes can spawn
new processes. However, a process can be destroyed,
by itself or by its parent, only when it is not in the
enrolement phase. Further, when a process p j creates
a new child that is capable of playing role r of
I, it informs each existing process p i 2 P(I) of the
identity of the new process so that p i can update
its P(r). In return, p i sends p j an acknowledgement
message, having timestamp t i . p j sets the
logical clock of the new process to be larger than
all the t i 's. While waiting for its parent to set its
clock, the new child defers any capture requests
that may arrive. These deferred requests will then
be rejected by the new process when its clock is
finally set. Similarly, when a process p j 2 P(I) is
destroyed, it informs the existing processes in P(I)
to remove p j from their P(I).
Since a process is not destroyed when it is in
the enrolement phase, the safety property of Theorem
1 is still guaranteed. The liveness property
holds as well because a newly created process p j is
always younger than any existing coordinator p i .
Hence, is unable to
contend with p i in capturing a slave (see Section 3).
Also, need not attempt to capture p j -such an
attempt is doomed to fail anyway as a coordinator
cannot capture a younger slave. Therefore, p i need
only request capture of those processes created before
its current enrolement phase. For-
tunately, this set of processes is finite.
8 Conclusion
We have presented an efficient distributed algorithm
for the first-order guard scheduling problem,
the first such algorithm of which we are aware.
We have also described several extensions of the
algorithm including generic roles, direct-partners-
named enrolement, and dynamically changing environments

Up to now, we have not addressed the possibility
of allowing enrolement statements within roles.
This leads to a notion of nested enrolement -an
nth-order interaction, if you will. Nested enrole-
ment exists in some form already in IP and Script.
Our algorithm can be safely applied at each level
of enrolement: level n enrolement will involve roles
of level are eventually filled by actual
processes, reducing the problem to first-order en-
rolement.
Future work will focus on lowering the constant
of the message complexity, currently O(6m), and
finding a probabilistic, completely symmetric solution
to the problem.

Acknowledgement

We thank Prof. Nissim Francez
for providing us with several references on IP and
some valuable insights into the language; and Shaji
Bhaskar for his constructive comments on the presentation
of the algorithm.



--R

"Distributed cooperation with action systems,"
"Process synchronization: design and performance evaluation of distributed algorithms,"
A Foundation of Parallel Program Design
"On the design of large distributed systems,"
private communication
"Conflict propaga- tion,"
Interacting Pro- cesses: A Multiparty Approach to Coordinated Distributed Programming
"Interacting Pro- cesses: A language for coordinated distributed pro- gramming,"
"Script: A communication abstraction mecha- nism,"
Computers and Intractability: A Guide to The Theory of NP- completeness
"An n 5=2 algorithm for maximum matching in bipartite graph,"
"Efficient, dynamically structured multiprocess communication,"
"An implementation of N-party synchronization using tokens,"
"Time, clocks and the ordering of events in a distributed system,"
"A distributed synchronization scheme for fair multi-process hand- shakes,"
"A new class of high-level programs for distributed computing systems,"
"A new and efficient implementation of multiprocess synchronization,"
--TR
Script: a communication abstraction mechanism and its verification
The multiway rendezvous
A new and efficient implementation of multiprocess synchronization
Appraising fairness in distributed languages
Distributed cooperation with action systems
Parallel program design: a foundation
Communication and concurrency
Synchronization of asynchronous processes in CSP
Process Synchronization
Multiparty Interactions for Interprocess Communication and Synchronization
A distributed synchronization scheme for fair multi-process handshakes
Fairness and hyperfairness in multi-party interactions
Interacting processes: a language for coordinated distributed programming
On the design and implementation of multiparty interaction
A comprehensive study of the complexity of multiparty interaction
Interacting processes
Time, clocks, and the ordering of events in a distributed system
Communicating sequential processes
Solution of a problem in concurrent programming control
A New Class of High Level Programs for Distributed Computing Systems

--CTR
Yuh-Jzer Joung , Scott A. Smolka, Strong Interaction Fairness Via Randomization, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.137-149, February 1998
Yuh-Jzer Joung, On strong-feasibilities of equivalence-completions, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.156-165, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Yuh-Jzer Joung , Scott A. Smolka, A comprehensive study of the complexity of multiparty interaction, Journal of the ACM (JACM), v.43 n.1, p.75-115, Jan. 1996
multiparty interaction;rendezvous;interaction scheduling;distributed languages;committee coordination;distributed algorithms;first-order interaction