Strong Interaction Fairness Via Randomization.
AbstractWe present MULTI, a symmetric, distributed, randomized algorithm that, with probability one, schedules multiparty interactions in a strongly fair manner. To our knowledge, MULTI is the first algorithm for strong interaction fairness to appear in the literature. Moreover, the expected time taken by MULTI to establish an interaction is a constant not depending on the total number of processes in the system. In this sense, MULTI guarantees real-time response. MULTI makes no assumptions (other than boundedness) about the time it takes processes to communicate. It, thus, offers an appealing tonic to the impossibility results of Tsay and Bagrodia, and Joung concerning strong interaction fairness in an environment, shared-memory, or message-passing, in which processes are deterministic and the communication time is nonnegligible. Because strong interaction fairness is as strong a fairness condition that one might actually want to impose in practice, our results indicate that randomization may also prove fruitful for other notions of fairness lacking deterministic realizations and requiring real-time response.
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. Although a
relatively new concept, the multiparty interaction has found its way into various distributed programming
languages and algebraic models of concurrency. See [11] for a taxonomy of programming
languages offering linguistic support for multiparty interaction.
Although multiparty interactions are executed synchronously, the underlying model of communication
is usually asynchronous and bipartied. The multiparty interaction scheduling problem then
is concerned with synchronizing asynchronous processes to satisfy the following requirements: (1) an
interaction can be established only if it is enabled (i.e., all of its participants are ready), and (2) a
process can participate in only one interaction at a time. Moreover, some notion of fairness is typically
associated with the implementation to prevent "unfair" computations that favor a particular
process or interaction.
Several important fairness notions have been proposed in the literature [1, 2, 3], including: weak
interaction fairness, where if an interaction is continually enabled, then some of its participants
will eventually engage in an interaction; and strong interaction fairness, where an interaction that
is infinitely often enabled will be established infinitely often. A distinguishing characteristic of
interaction fairness is that it is much weaker than most known fairness notions, while strong
interaction fairness is much stronger.
In general, stronger fairness notions induce more liveness properties, but are also more difficult
to implement. Therefore, it is not surprising to see that only weak interaction fairness has been
widely implemented (e.g., [18, 15, 4, 14, 12, 20, 10]). It is also not surprising to see that all of
these algorithms are asymmetric and deterministic, as weak interaction fairness (and thus strong
interaction fairness) has been proven impossible by any symmetric, deterministic, and distributed
algorithm [8, 13]. Given that a process decides autonomously when it will attempt an interaction,
and at a time that cannot be predicted in advance, strong interaction fairness is still not possible
even if the symmetry requirement is dropped [19, 9].
Note that these impossibility results do not depend on the type of communication primitives
(e.g., message-passing or shared-memory) provided by the underlying execution model. They hold
as long as one process's readiness for multiparty interaction can be known by another only through
communications, and the time it takes two processes to communicate is nonnegligible (but can be
finitely bounded).
In the case of CSP communication guard scheduling, a special case of the multiparty interaction
scheduling problem where each interaction involves exactly two processes, randomization has proven
to be an effective technique for coping with the aforementioned impossibility phenomena. For ex-
ample, the randomized algorithm of Reif and Spirakis [17] is symmetric, weak interaction fair with
probability 1, and guarantees real time response: if two processes are continuously willing to interact
with each other within a time interval \Delta, then they establish an interaction within \Delta time with high
likelihood, and the expected time for establishment of interaction is constant.
The randomized algorithm of Francez and Rodeh [8] is simpler: a process p i expresses its willingness
to establish an interaction with a process p j by setting a Boolean variable shared by the two
may then need to wait a certain amount of time ffi before reaccessing the variable to
determine if p j is likewise interested in the interaction. The authors show that, under the proviso
that the time to access a shared variable is negligible compared to ffi, the algorithm is weak interaction
fair with probability 1. Note, however, that this assumption, combined with the fact that no lower
bound on ffi is provided, may significantly limit the algorithm's practicality. Furthermore, no strong
interaction fairness is claimed by either algorithm.
In this paper, we present Multi, an extension of Francez and Rodeh's randomized algorithm to
the multiparty case. We prove that Multi is weak interaction fair with probability 1. We also show
that if the transition of a process to a state in which it is ready for interaction is independent of the
random draws of the other processes, then, with probability 1, Multi is strong interaction fair. To
our knowledge, Multi is the first algorithm for strong interaction fairness to appear in the literature.
We also present a detailed timing analysis of Multi and establish a lower bound on how long a
process must wait before reaccessing a shared variable. Consequently, our algorithm can be fine-tuned
for optimal performance. Moreover, we show that the expected time to establish an interaction is a
constant not depending on the total number of processes in the system. Thus, Multi also guarantees
real-time response.
Because strong interaction fairness is as strong a fairness condition that one might actually want
to impose in practice, our results indicate that randomization may also prove fruitful for other notions
of fairness lacking deterministic realizations and requiring real-time response.
The rest of the paper is organized as follows. Section 2 describes the multiparty interaction
scheduling problem in a more anthropomorphic setting known as Committee Coordination. Our
randomized algorithm is presented in Section 3 and analyzed in Section 4. Section 5 concludes.
2 The Committee Coordination Problem
The problem of scheduling multiparty interactions in asynchronous systems has been elegantly characterized
by Chandy and Misra as one of Committee Coordination [5]:
Professors (cf. processes) in a certain university have organized themselves into committees
(cf. interactions) and each committee has a fixed membership roster of one or more
professors. From time to time, a professor may decide to attend a committee meeting;
it starts waiting and continues to wait until a meeting of a committee of which it is a
member is established.
To state the Committee Coordination problem formally, we need the following two assumptions:
(1) a professor attending a committee meeting will not leave the meeting until all other members of
the committee have attended the meeting; and (2) given that all members have attended a committee
meeting, each committee member leaves the meeting in finite time. The problem then is to devise
an algorithm satisfying the following three requirements:
Synchronization: When a professor attends a committee meeting, all other members of the committee
will eventually attend the meeting as well.
Exclusion: No two committees meet simultaneously if they have a common member.
Weak Interaction Fairness: If all professors of a committee are waiting, then eventually some
professor will attend a committee meeting.
We shall also consider strong interaction fairness, i.e., a committee that is infinitely often
enabled will be established infinitely often. A committee is enabled if every member of the committee
is waiting, and is disabled otherwise.
The overall behavior of a professor can be described by the state transition diagram of Figure 1,
where state T corresponds to thinking, W corresponds to waiting for a committee meeting, and E
means that the professor is actively engaged in a meeting.
Note that any algorithm for the problem should only control the transition of a professor from
state W to state E, but not the other two transitions. That is, the transitions from T to W and from
to T are autonomous to each professor. Moreover, we do not assume any upper bound on the time
'i
'i
'i
meeting
start meeting
ready for
finish
meeting

Figure

1: State transition diagram of a professor.
a professor can spend in thinking. Otherwise, an algorithm for the problem could simply wait long
enough until all professors become waiting, and then schedule a committee meeting of its choosing.
All three requirements for the problem and strong interaction fairness would then be easily satisfied.
3 The Algorithm
In this section, we present Multi, our randomized algorithm for committee coordination. In the
algorithm, we associate with each committee M a counter CM whose value ranges over [0 \Delta \Delta jprof.Mj
\Gamma1], where prof :M is the set of professors involved in M . CM can be accessed only by the professors
in prof :M and only through the TEST&OP instruction as follows:
result := TEST&OP(CM , zero-op, nonzero-op)
The effect of this instruction is to apply to CM the operation zero-op if its value is zero and the
operation nonzero-op otherwise, and to assign to the variable result the old value (i.e., the value
before the operation) of CM . The operations used here are no-op, inc, and dec, where
For example, if returns 2. If
TEST&OP(CM , no-op, dec) leaves CM unchanged and returns 0. To simplify the presentation of the
algorithm, we assume that the execution of the TEST&OP instruction is "atomic." This assumption
is removed in Section 4.4, where a more concurrent implementation of TEST&OP is considered.
Algorithm Multi can be informally described as follows. Initially, all the shared counters are
set to zero. When a professor p i decides to attend a committee meeting, it randomly chooses a
committee M of which it is a member. It then attempts to start a meeting of M by increasing the
value of CM by 1 (all increments and decrements are to be interpreted modulo jprof.Mj). If the new
value of CM is 0 (i.e., before the increment), then professor p i concludes that
each of the other members of M has increased CM by one, and is waiting for p i to convene M . So
goes to state E to start the meeting.
If the new value of CM is not zero, then at least one of the professors in prof.M is not yet ready.
waits for some period of time (hoping that its partners will become ready) and then
reaccesses CM . If CM has now been set to 0, then all the professors which were not ready for M are
now ready, and so p i can attend the meeting. If CM is still not zero, then some professor is still not
ready for M . So p i withdraws its attempt to start M by decreasing the value of CM by 1 and tries
another committee.
The algorithm to be executed by each professor p i is presented in Figure 2, where waiting (line 1)
is a Boolean flag indicating whether or not p i is waiting for a committee meeting. The constant ffi
(line is the amount of time a professor waits before reaccessing a counter. We will later require
(see Section 4) that ffi be greater than is the maximum amount of
time a professor can spend in executing lines 2 and 3. 1 Note that the algorithm is symmetric in the
sense that all professors execute the same code and make no use of their process ids.
4 Analysis of the Algorithm
In this section we prove that Multi satisfies the synchronization and exclusion requirements of the
Committee Coordination problem, and, with probability 1, is weak and strong interaction fair. We
also analyze the expected time Multi takes to schedule a committee meeting.
4.1 Definitions
We assume a discrete global time axis where, to an external observer, the events of the system are
totally ordered. Internally, however, processors may execute instructions simultaneously at the same
time instance. Simultaneous access to a shared counter will be arbitrated in the implementation of
precisely, jmax should also include the time it takes to execute line 1. To simplify the analysis, we assume
that the Boolean flag waiting only serves to indicate the state of the executing professor, and so no explicit test of the
flag is needed. Moreover, we assume that an action is executed instantaneously at some time instance. The time it
takes to execute an action is the difference between the time the action is executed and the time the previous action
(of the same professor) was executed.
1. while waiting do f
2. randomly choose a committee M from fM j
3. if TEST&OP(CM , inc,
4. then /* a committee meeting is established */
5. attend the meeting of M
6. else f wait
7. if TEST&OP(CM , no-op,
8. then /* a committee meeting is established */
9. attend the meeting of M ;
10. /* else try another committee */ g
11. g

Figure

2: Algorithm Multi for professor p i .
the TEST&OP instruction, which we assume is executed atomically.
Since the time axis is discrete, it is meaningless to say that "there are infinitely many time
instances in some finite time interval such that ." Therefore, throughout this paper, the phrase
"there are infinitely many time instances" refers to the interval [0; 1).
For analysis purposes, we present in Figure 3 a refinement of the state transition diagram of Figure
1, where state W is refined into three sub-states . The actions taken by the professors
from these sub-states are:
randomly choose a new committee.
execute the instruction TEST&OP(CM ; inc; inc).
executing the instruction TEST&OP(CM ; no-op; dec).
We say that a professor accesses counter CM when it executes the TEST&OP instruction of state W 1 ,
reaccesses CM when it executes the TEST&OP instruction of state W 2 , and monitors committee M
while it is in state W 2 waiting for reaccess to CM .
According to the algorithm, if at time t a professor p accesses a counter CM by TEST&OP(CM ; inc; inc)
in state W 1 , then it will be in state W 2 or E right after 2 t, depending on the value of CM . Further-
2 If an action, which transits a professor p from state s1 to state s2 , occurs at time t, then we say that p is in state
s1 just before t, and is in state s2 right after t. For p's state to be defined at every time instance, we stipulate that p's
'i
'i
'i
'i
'i
ready for
meeting
reaccess CM (=0)
access CM
draw
finish
meeting
access CM
reaccess CM (6=
random

Figure

3: State transition diagram of a professor executing the algorithm.
ffistart waitingrandom drawrandom drawrandom draw

Figure

4: Timing constraints on the actions executed by a professor.
more, if p enters state W 2 at time t to monitor a committee M , then at time t reaccess
CM by TEST&OP(CM ; no-op; dec). Depending on the value of CM , after time the professor will
either return to state W 0 to choose another committee, or enter state E to attend the meeting of M .
In executing algorithm Multi, a professor starts waiting for a committee meeting in state W 0
and then repeatedly cycles through states W 0 through W 2 until entering a committee meeting via a
transition from state W 1 or W 2 . The actions it performs along this cycle are subject to the timing
constraints depicted in Figure 4. In particular, the interval between consecutive access and reaccess
actions must be of length ffi, while the interval between consecutive reaccess and access actions must
have length no greater than j max . We shall sometimes refer to the former as a "ffi-interval." As will
be made explicit in Section 4.3, the duration of a ffi-interval may vary from iteration to iteration of
the algorithm; we will require only that ffi is greater than a lower bound determined by j max and the
number of professors in the committee currently under consideration.

Figure

5 illustrates a possible scenario for four professors executing the algo-
state at time t is s2 if p executes the action at time t. For example, if p accesses CM at time t and then reaccesses CM
at time t is in state W2 at any time instance in [t; t ffi). Note that the interval is open at t + ffi. So if we
say that p is in state W2 at time t, then p must have accessed CM at some time in
prof
prof
Echoose M 14choose M 123choose M 123T
Echoose M 234choose M 234choose M 123T
Echoose M 123choose M 234choose M 123T
Echoose M 14choose M 234choose M 14

Figure

5: A partial computation of four professors.
rithm, where p 1 and p 4 are involved in committee M 14 , are involved in M 123 , and p 2 ,
are involved in M 234 . For each professor, we explicitly depict its state (on the Y-axis) at
each global time instance (on the X-axis). For example, at time 1 professor p 1 starts waiting for a
committee meeting and so it enters state W 0 from state T . At time 2, it randomly chooses M 14 and
then accesses CM 14 at time 3. Since CM before the access, p 1 enters state W 2 to monitor M 14
for units and then reaccesses CM 14
at time 6. Since p 4 will not access CM 14
returns to state W 0 to try another committee. Later at time 12, p 1 chooses committee M 123 and
then accesses CM 123 at time 13. When p 1 reaccesses CM 123 at time 16, it finds that both p 2 and p 3
are willing to start the meeting of M 123 . So p 1 enters state E to attend the meeting. The meeting of
123 ends at time 19, after which the committee members can return to state T at a time of their
own choosing. The shaded area between time 17 and 19 represents a synchronization interval for the
three professors.
4.2 Properties of the Algorithm That Hold with Certainty
We now analyze the correctness of the algorithm. We begin with an invariant about the value of a
shared counter CM , which we will use in proving that Multi satisfies the synchronization condition
of the Committee Coordination Problem.
Lemma 1 If at time t there are k professors in state W 2 monitoring committee M and no professor,
since last entering state W 0 , has entered state E to attend a meeting of M , then the value of CM at
time t is k and k ! jprof :M j. If, however, at time t some professor has entered state E to attend a
meeting of M , then professors in prof :M will have entered state E to
attend the meeting of M .
Proof: We prove the lemma by induction on t i , the time at which the i th system event occurs. The
lemma holds at time t 0 because initially every professor in prof :M is in state T and
the induction hypothesis, assume the following at time t
prof :M is the set of professors in
state W 2 monitoring committee M , no professor, since last entering state W 0 , has entered state E
to attend a meeting of M , and
Consider now the nearest time t j , j - i, at which some professor p accesses or reaccesses CM .
Since no professor accesses or reaccesses CM in [t the induction hypothesis holds as well in this
interval. Suppose first that p accesses CM through the instruction TEST&OP(CM ; inc; inc). If before
the access CM ! jprof after the access (which is less than jprof
and p enters state W 2 . That is, after time t j there are jQj professors in state W 2 monitoring
committee M , and Conversely, if before the access after the
access enters state E. Since just before t j the other professors in Q are all monitoring
M , by time reaccessed CM by TEST&OP(CM ; no-op; dec). Moreover, when they
reaccess CM they will find that CM = 0 and so they will all enter state E to start M .
To see why this last statement is true, recall that by the first of the two assumptions we put forth
in defining the Committee Coordination problem (Section 2), no professor attending M will leave M
before all of M 's members have entered state E to attend M . Consequently, no professor attending
M can leave M to attempt another instance of M (by accessing CM ), from which the desired result
follows.
Suppose now that p reaccesses CM through the instruction TEST&OP(CM ; no-op; dec). Then p 2 Q.
Since CM 6= 0, right after p's reaccess, returns to state W 0 . So right after t j ,
professors are in state W 2 monitoring M . 2
Theorem 1 (Synchronization) If a professor in prof :M enters state E at time t to attend a
meeting of M , then within ffi time all professors in prof :M will have entered state E to attend the
meeting of M .
Proof: The theorem follows immediately from Lemma 1. 2
Theorem simultaneously if they have a common member

Proof: The result follows from the fact that a professor monitors one committee at a time. 2
4.3 Properties of the Algorithm That Hold with Probability 1
We move on to prove that Multi is weak and strong interaction fair, and analyze its time complexity.
For this we need the the following two assumptions:
A1: The ffi-interval a professor chooses to wait for committee M satisfies the condition
is the maximum amount of time a professor can spend in executing lines 2 and 3
of Multi.
A2: A professor's transition from thinking to waiting (see Figure 1) does not depend on the random
draws performed by other professors.
Note that A2 is required only for strong interaction fairness.
We also require some definitions about the "random draw" a professor performs in state W 0 when
deciding which meeting to attempt. Recall that we say that a professor accesses a counter CM when
it executes the instruction TEST&OP(CM ; inc, inc) (line 3 of the algorithm) and reaccesses CM when
it executes TEST&OP(CM , no-op, dec) (line 7). Now suppose that professor p accesses some counter
in the time interval there is more than one such access, choose the most recent one. Then
the choice of counter must be the result of the random draw performed before the access (line 2).
Let D t;p denote this random draw; D t;p is not defined if p does not access any counter in
Furthermore, let D t;prof prof :M and D t;p is defined g.
For example, if p is in state W 2 at time t, then p must have accessed some counter in the interval
must be defined. As we shall see in Lemma 4, the definition of D t;p guarantees
that if D t;p is defined for all p 2 prof :M and these random draws yield the same outcome M , then
M will be established.
Henceforth we shall use / p;M to denote the fixed non-zero probability that professor p 2 prof :M
chooses committee M in a random draw. Thus,
Y
p2prof :M
is the probability that a set of mutually independent random draws, one by each professor in prof :M ,
yields the same outcome M .
The following three lemmas are used in the fairness proofs. The first one says that D t;prof :M and
must refer to mutually disjoint sets of random draws if t and t 0 are at least ffi apart.
Proof: Directly from the definition of D t;p . 2
Lemma 3 Assume A1 and that committee M is continuously enabled in the interval
is, M is enabled at any time instance in [t there exists a time
instance t, t
Since M is continuously enabled in [t every professor of M is, by definition, in a
-state throughout this interval. Clearly, either one of the following holds:
such that p is in state W 2 throughout
such that p is in state W 0 or W 1 throughout
In case (i), let t g. Then D t;p is defined for every p 2 prof :M and every
Given that t and that ' - j max , we thus have that there exists some t,
j. So the lemma is proven.
For case (ii), suppose that some professor p 1 2 prof :M stays in W 0 or W 1 in [t
then accesses some counter at t i +m 1 , where
by the assumed lower bound on ', t
If D t i +m 1 ;p is defined for all p 2 prof :M , then we are done. Otherwise, there must exist another
professor 2. By the lower bound on ',
still enabled at time t i +m 1 . So p 2 is in a W-state at t i +m 1 .
cannot be in state W 2 , for otherwise D t i +m 1 ;p 2
would be defined. So p 2 is in state W 0 or
must access some counter within j max time. Assume that p 2 accesses some counter at
We argue that D t i +m 1 +m 2 ;p 1
is also defined. To see this, recall that
By the lower bound on ' and the fact that jprof :M j - 2, we have
still in a W -state at any time instance in
some counter at t i +m 1 , p 1 must have entered state W 2 after the access, and stays in W 2 throughout
must be defined for all t in [t i and the fact
that
Note that t defined for every other professor
in prof :M , then we are done. Otherwise, similar to the above reasoning, there must exist a third
professor prof :M such that D t i +m 1 +m 2 ;p 3 is not defined. Using the same argument, we can show
that there exists m 3 where
is defined for all
Continuing in this fashion, we can show that there exists k professors in prof :M , and
and D t i +m 1 +m 2 +:::+m k ;p l is defined for all 1 - l - k. Given that there are only a finite number of
professors in prof :M , eventually we will establish that there exists some t, t
D t;p is defined for each p 2 prof :M . The lemma is then proven. 2
The proof of Lemma 3 is illustrated in Figure 6 for a committee of size 4 with t
the smallest ffi allowed by A1.
As a consequence of Lemma 3, different professors can choose different values for ffi; these values
need only satisfy the lower bound established by A1. 3 Therefore, the clocks used by the professors
to implement time-outs need not be adjusted to the same accuracy.
Lemma 3 says that, under assumption A1, if a committee M is continuously enabled sufficiently
long, then there exists an interval of length ' within which every professor in prof :M performs a
random draw. The following lemma ensures that if their random draws yield the same outcome,
then they must establish M .
Lemma 4 If jD t;prof :M all the random draws in D t;prof :M yield the same outcome
3 As such, the ffi referred to in the definition of D t;prof :M and in the statement of Lemma 1 should be understood as
the minimum and the maximum of the relevant ffi values, respectively.
M is continuously enabled
\Gammareadyaccessreaccess
\Gammareaccessaccess
\Gammareaccessaccess
access

Figure

Illustration of the proof of Lemma 3. is the maximum possible interval throughout
which M is enabled but jD t;prof:M j 6= jprof:M j. Here jprof:M must be defined for all
. Note that if ffi min would equal
would not be defined.
M , then by time t some professor must have already entered state E to start M , and by time
all professors in prof :M will enter state E to start M .
Proof: Assume the hypotheses described in the lemma. Let p i 2 prof :M be the first professor
which, after performing its random draw in D t;prof :M , accesses CM by TEST&OP(CM ; inc; inc), and
prof :M be the last professor to do so. Let t i and t j be the time at which p i and p j ,
respectively, access CM . Then, t.
CM at time t i , it will not reaccess CM until
professors that access CM in [t remain in state W 2 before p j accesses CM . By Lemma 1,
just before access. So when p j accesses CM at t j , it will set CM to zero and
enter state E to start M . Moreover, by time ffi, every other professor of M will learn that M
has been started when it reaccesses CM by TEST&OP(CM ; no-op; dec), and so will also enter state E
to start M . Since ffi, the lemma is thus established. 2
Note that Lemma 4 relies on the fact that the access involved in the definition of D t;p occurs in
the interval that is open at and closed at t. If we were to relax the definition to the
closed interval then the correctness of Lemma 4 would depend on how an access/reaccess
conflict to the same counter is resolved in the implementation. To see this, suppose that p 1 accesses
a counter at a counter at t. So by the new definition both D t;p 1
and D t;p 2
are defined. Suppose further that both random draws yield the same outcome M , which involves
only access the same counter CM at t, respectively. Assume that
before By the algorithm, p 1 will wait ffi time and then reaccess CM at t, causing
a conflict with p 2 's access at the same time. Clearly, M will be established only if the conflict is
resolved in favor of the access; i.e., p 2 gets to go first.
Theorem 3 (Weak Interaction Fairness) Assume A1 and that all members of a committee M
are waiting for committee meetings. Then the probability is 1 that eventually a meeting involving
some member of M will be started.
Proof: Assume A1, and suppose that M is enabled at t. Let
jprof :M j. Consider the probability that M is continuously enabled in [t; t
M is continuously enabled in [t; t exists a time instance t 1 ,
that jD t 1 ;prof :M j. If the random draws in D t 1 ;prof :M yield the same outcome M , then, by
Lemma 4, M must be disabled at t 1 . (Even if the random draws do not yield the same outcome,
some professor of M may still establish another committee meeting M 0 if its random draw has the
outcome M 0 and at the same time all other professors of M 0 are also interested in M 0 .) So the
probability that the random draws in D t 1 ;prof :M do not cause any committee involving a member of
M to be started is no greater than and so the probability that M is continuously enabled
in [t; t
Similarly, if M is still enabled after t 1 , then by Lemmas 2 and 3 there must exist another time
instance t 2 such that D t 2 ;prof :M contains a completely new set of random draws of size jprof :M j.
Again, the probability that M remains enabled after these random draws is no greater than
given that the random draws in D t 1 ;prof :M do not cause any member of M to attend a meeting. So
the probability that M is continuously enabled up to time t 2 is no greater than
if M is still enabled at t 2 then there will be another new set of random draws D t 3 ;prof :M of size
jprof :M j. In general, the probability that M remains continuously enabled after i mutually disjoint
sets of random draws D t 1 ;prof As i tends to infinity,
tends to zero. So the probability is zero that M remains enabled forever. 2
Intuitively, A1 requires that the ffi parameter used in the algorithm is large enough so that a
professor will not reaccess a counter before the other professors get a chance to access the counter.
reaccess 6
access 6
reaccess 6
access 6
reaccess
reaccess 6
access 6
reaccess 6
access 6
reaccess

Figure

7: Two professors wait forever without establishing a meeting due to a bad choice of ffi.
If this assumption is removed from Theorem 3, then a set of professors could access and reaccess
a counter forever without ever establishing a committee meeting. To illustrate, consider Figure 7.
Each professor reaccesses a counter before the other professor could access the same counter. So no
matter what committees they choose in their random draws, at no time can a professor see the result
of a counter set by the other professor.
The strong interaction fairness property of the algorithm additionally requires assumption A2
and a lemma on the probabilistic behavior of a large number of random draws.
Lemma 5 Assume A2. If there are infinitely many t's such that jD t;prof :M then the
probability is 1 that all the random draws in D t;prof :M produce the same outcome for infinitely many
t's.
be an infinite sequence of increasing time instances at which jD t i ;prof :M
jprof :M j. W.l.o.g. assume that 8i; t 2, the sets D t i ;prof :M are pairwise
disjoint.
Consider the random draws in set D t i ;prof :M . Let EM denote the event that the random draws in
produce the same outcome M . By A2, the probability of EM 's occurrence is independent
of the time these random draws are made and is given by /M . Define random variable A i to be 1
if EM occurs at t i , and 0 otherwise. Then A
By the Law of Large Numbers (see, for example, [6]), for any ffl we have
lim
That is, when n tends to infinity, the probability is 1 that
n tends to /M . Therefore, with
probability 1, the set fi j A Hence, with probability 1, there are infinitely
many i's such that the random draws in D t i ;prof :M produce the same outcome M . 2
Theorem 4 (Strong Interaction Fairness) Assume A1 and A2. Then if a committee is enabled
infinitely often, with probability 1 the committee will be convened infinitely often.
Proof: Since the algorithm satisfies weak interaction fairness, we assume that there are infinitely
many i's such that M becomes enabled at time instance t i . Let either (1) there
are infinitely many i's such that M is continuously enabled in each interval [t or (2) starting
from some point t i 0 onward, whenever M becomes enabled at t i , some professor in prof :M attends
a committee meeting in the interval
Consider Case (1). By Lemma 3 and A1, there are infinitely many i's such that each interval
contains some time instance t such that jD t;prof :M j. Then by Lemma 5 and A2,
with probability 1 there are infinitely many t's such that all the random draws in D t;prof :M produce
the same outcome. So by Lemma 4, with probability 1 M is convened infinitely often.
Consider Case (2). W.l.o.g. assume each interval (t contains no time instance t such that
by the previous argument we can also show that M will be
convened infinitely often with probability 1. Let Q prof :M be the set of professors that have
accessed a counter between the time t i at which they are waiting for M until the time at which
they attend a committee meeting. For each q 2 Q i , let a be q's first such access, and let D 1
denote q's random draw performed right before a. For each
p's latest random draw performed before time t i . Note that since p is in a W -state at t i , D 2
defined and its outcome must cause p to attend a committee meeting at some time after t i . Let
g. By A2, the random draws in D 0
are
mutually independent and have a nonzero probability /M to yield the same outcome M . Therefore,
by the Law of Large Numbers (see the proof of Lemma 5), the probability is 1 that there are infinitely
many i's such that all the random draws in D 0
yield the same outcome M . If all the random
draws in D 0
yield the same outcome M , then either a meeting of M will be established, or
each professor in prof :M will still be waiting for M and will perform another random draw to access
a new counter. By a technique similar to Lemma 3, it can be seen that in the later case we would
be able to find a time instance t in (t j. By the assumption
of the case, we conclude that with probability 1 M is convened infinitely often. 2
Note that if Assumption A2 is dropped from Theorem 4, then a conspiracy against strong inter-action
fairness can be devised. To illustrate, consider a system of two professors p 1 and p 2 , and three
committees involving only involving only p 2 , and M 12 , which involves both p 1 and p 2 .
Suppose that p 1 becomes waiting, and then tosses a coin to choose either M 1 or M 12 . The malicious
could remain thinking until p 1 has selected M 1 ; then p 2 becomes waiting just before
random draw is performed only if p 1 's latest random draw yields outcome
once it selects M 1 , M 12 will not be started if p 1 remains in
its meeting while p 2 is waiting. However, M 12 is enabled as soon as p 2 becomes waiting. Similarly,
could also remain thinking until p 2 has selected M 2 . So if this scenario is repeated ad infinitum,
then the resulting computation would not be strong interaction fair.
The time complexity of the algorithm is analyzed in the following theorem, which assume a worst
case scenario that a professor spend j max time in executing lines 2 and 3 of Multi.
Theorem 5 (Time Complexity) Assume that each professor spends j max time in executing lines 2
and 3 of Multi, and assume A1, i.e., the amount of time ffi a professor spends in monitoring an
interaction is greater than 1). Then the expected time it takes any member of a
committee M to start a meeting from the time that M becomes enabled is no greater than
Proof: Suppose that M becomes enabled at time t. Consider first that there exists a time instance
Assume first that while M is
enabled, no conflicting committee is enabled simultaneously. (Two committee conflict if they share
a common member.) So when M is enabled, each professor in prof :M can only attend a meeting of
M .
By Lemma 4, if the random draws in jD t 1 ;prof :M j yield the same outcome M (an event that
occurs with probability /M ), then some professor in prof :M will start a meeting of M by time t 1 .
Otherwise, each professor in prof :M must perform another random draw and access the selected
counter within j (from the time it reaccesses the previous selected counter). So there must
exist another time instance t 2 , contains a completely new
set of random draws, one by each professor in prof :M . Once again, if the new random draws yield
the same outcome M , then some professor will start a committee meeting. So the probability that
M will be disabled by time t 2 is
In general, let D t i ;prof :M be the i th set of random draws performed by the professors, where
ffi). Then the probability that M will be disabled by time t i is
ffi). So the expected
time starting from t until some member of M enters state E to start a meeting is no greater than
We assumed above that no committee conflicting with M can be enabled while M is enabled; this
implies that for each set of random draws D t i ;prof :M , the random draws must yield the same outcome
M for the members of M to start a meeting. If a conflicting committee is enabled simultaneously,
then some of the random draws in D t i ;prof :M may still lead to a committee meeting even if they do
not yield outcome M . Hence, the expected time starting from t until some member of M enters state
E to start a meeting will actually be less than (j conflicting committee is enabled
simultaneously.
Assume next that there exists no time instance t 1 ,
must be disabled before t
's disabledness must be the result of some professor's random draw leading to the establishment
of some committee meeting involving that professor. So the disabling of M at some time before
must also be a probabilistic event. Therefore, in this case the expected time
starting from t until some member of M enters state E to start a meeting is no greater than
j. Given that that the expected time is
no greater than
Therefore, in either case, the expected time starting from t until some member of M enters state
E to start a meeting is no greater than (j
Intuitively, Theorem 5 states that the expected time for any member of prof :M to start a committee
meeting when they are all waiting is no greater than the amount of time to execute one round
of the while-loop of Multi (i.e., divided by the probability that these professors in their
random draws all choose the same committee M (i.e., /M ).
Note that j max is a constant determined by the size (number of members) of the largest committee.
Call this value S max and let j . The probability /M is a constant determined by the
size of M , and the maximum number of committees of which a professor can be a member (call
this value C
p2prof :M /
Finally, ffi is a constant determined by
Therefore, the time complexity of the algorithm is bounded by
the following constant:
While in the worst case S max could be equal to the total number of professors, and C max could
be equal to the total number of committees in the system (which, in turn, could be dependent on
the total number of professors), in practice, it is generally known that both parameters must be kept
small and independent of the total number of professors in the system [7]. 4
In contrast, deterministic algorithms for Committee Coordination such as [15, 12, 10] have time
complexity
where c 0 is a constant and N is the total number of professors in the system. 5 The time complexity
of these algorithms depends explicitly on N because they use priority to beak the symmetry among
professors. As such, a lower priority professor may have to wait for a higher priority professor if they
attempt to establish a conflicting committee, and the higher priority professor in turn may have to
wait for another higher priority professor, and so on. (Recall, Section 1, that there is no symmetric,
deterministic, and distributed solution for Committee Coordination.)
If C max and S max are kept small and independent of N , then Multi, in addition to guaranteeing
strong interaction fairness, out-performs deterministic algorithms while providing real-time response.
4.4 A Non-Atomic Implementation of TEST&OP
As promised in Section 3, we now present a non-atomic, and hence more concurrent, implementation
of the TEST&OP instruction. Recall that the execution of the statement TEST&OP(CM , zero-op,
nonzero-op) actually involves two 6 actions: read CM , then apply to CM the operation zero-op if
and the operation nonzero-op otherwise. More precisely, the actions are read followed
by inc when a professor executes TEST&OP(CM ; inc; inc) to access a counter, and read followed by
dec/no-op when it executes TEST&OP(CM ; no-op; dec) to reaccess the counter.
Clearly, we can apply a mutual exclusion algorithm (see [16] for a survey) to ensure that each
access and reaccess to a counter proceeds atomically. This, however, is an overkill. For example,
4 A scheme of synchrony loosening is therefore proposed in [7] for reducing the size of an interaction in practical
applications.
5 These algorithms and Multi all allow professors to distributedly establish a committee meeting on their own. Other
deterministic algorithms such as [5, 4, 14] employ "managers" to coordinate committee meetings; the time complexity
of these algorithms then depends on the number of managers they use.
6 Three, if you count the Boolean test.
accesses to a counter can be executed concurrently. 7 To see this, consider three possible interleaved
executions of two TEST&OP(CM ; inc; inc)'s:
read 1 , read 2 , inc 1 , inc 2
read 1 , read 2 , inc 2 , inc 1
read 1 , inc 1 , read 2 , inc 2
Observe that the first two executions have the same effect: both will cause the executing professors
to enter state W 2 to monitor M because the value of CM returned by both reads is less than
value before the two accesses is less than jprof then the third
execution, in which the two accesses proceed atomically, will also have the same effect.
If CM 's value before the two accesses is jprof :M \Gamma 2j, then in the third execution the professor
executing the first access will enter W 2 to monitor M , while the other professor will enter state E
to start a meeting of M . When the first professor's ffi-interval expires, it will learn that a meeting of
M has been established when it reaccesses CM , and so will also enter state E to start a meeting of
M . The situation is similar in the first two executions: both professors will enter state E to start
a meeting of M when they reaccess the counter. So all three interleaved executions preserve the
synchronization property of the algorithm. (Breaking the atomicity of TEST&OP clearly has no effect
to the algorithm's exclusion and fairness properties.)
Note that the system performance may be increased if we reverse the order of execution of the
read and inc actions in the implementation of TEST&OP(CM ; inc; inc). To see this, consider again
the case where two professors attempt to access CM simultaneously. The following are two possible
interleaved executions:
inc 1 , inc 2 , read 1 , read 2
inc 1 , inc 2 , read 2 , read 1
Suppose that CM 's value before the access is jprof after the two increments,
So each professor, upon reading the value of CM , learns that all professors of M are now interested
in M and can enter state E to start a meeting of M . Moreover, the new implementation of
7 We assume that basic machine-level instructions such as inc, dec, load , and store are executed atomically. Thus, if
two such instructions are executed concurrently, the result is equivalent to their sequential execution in some unknown
order.
8 When concurrent accesses to the same counter are allowed, more than one professor may access CM simultaneously
and then all enter state W2 to monitor M because CM ! jprof before the accesses. Likewise, Lemma 1, which
assumes that access to a counter is atomic, needs to be slightly changed to reflect the possibility that
professors in prof :M are in state W2 at the same time.
inc) still ensures Multi's synchronization property regardless of how the actions
of overlapping TEST&OP(CM ; inc; inc) instructions are interleaved. 9
Similarly, interleaving read and dec/no-op of different professors' reaccesses to the same counter
cannot invalidate the algorithm's synchronization property. Only simultaneous access and reaccess
to the same counter may conflict. To illustrate, suppose that p 1 wishes to access CM while p 2 wishes
to reaccess. Suppose further that the value of CM before the attempt is jprof
access proceeds atomically before p 2 's reaccess, both professors will enter state E to start the
meeting. However, if the four constituent actions are interleaved as follows:
read 2 , inc 1 , read 1 , dec 2
decrement CM
by one and go to state W 0 to select a new committee. On the other hand, since
before p 2 's decrement, it will discover that thus enter state E to start M . Hence, the
synchronization requirement is violated.
To ensure that access and reaccess to the same counter are mutually exclusive while at the same
time allowing concurrent accesses and concurrent reaccesses, we can implement TEST&OP(CM ; inc; inc)
and TEST&OP(CM , no-op; dec) using the algorithm shown in Figures 8 and 9. The algorithm is
based on Dekker's algorithm for the bi-process critical section problem [16] and, as discussed above,
now returns the new value of CM . CM access count is a counter recording the
number of professors that are attempting to access CM , while CM reaccess count records the number
of professors attempting to reaccess CM . Both counters are initialized to zero. Furthermore, variable
CM turn, initialized to access, is used for resolving conflicts between accesses and reaccesses.
It can be seen that a professor enters the critical section to access CM only if CM access count
only professors attempting to access CM may modify
CM access count , and they test CM reaccess count only when CM access count ? 0, it follows that
when some professor p enters the critical section to access CM , no other professor can simultaneously
enter the critical section to reaccess CM . Moreover, no professor can enter the critical section to
9 If this new implementation is adopted, then line 3 of Figure 2 needs to be changed to "if TEST&OP(CM ; inc; inc) = 0"
because TEST&OP(CM ; inc; inc) now returns the value of CM after the access. Note, however, that TEST&OP(CM , no-
op, dec) must still return the value of CM before the access. This is because if it returns the value of CM after the
access, then when the returned value is zero, the executing professor p i would not be able to tell if (1) only p i itself is
interested in M (so that p i should decrease CM by one and then return to state W0 to retry another committee), or
(2) all members in prof :M are interested in M (so that p i should leave CM unchanged and then enter state E to start
a meeting of M .)
1. inc (CM access count) ;
2. while CM reaccess count ? 0 do
3. if CM turn = reaccess then f
4. dec (CM access count) ;
5. while CM turn = reaccess do no-op ;
6. inc (CM access count) ; g
7. /* beginning of critical section */
8. inc(C M
9. return read(C M
10. /* end of critical section */
11. dec (CM access count) ;
12. if CM access count = 0 then CM turn := reaccess ;

Figure

8: Implementation of TEST&OP(CM ; inc; inc).
1. inc (CM reaccess count) ;
2. while CM access count ? 0 do
3. if CM turn = access then f
4. dec (CM reaccess count) ;
5. while CM turn = access do no-op ;
6. inc (CM reaccess count) ; g
7. /* beginning of critical section */
8. if read(C M
9. else f return read(C M
10. /* end of critical section */
11. dec (CM reaccess count) ;
12. if CM reaccess count

Figure

9: Implementation of TEST&OP(CM ; no-op; dec).
reaccess CM while p is already in the critical section but has not yet left the critical section. Similarly,
if a professor is in the critical section to reaccess CM , then no other professor can enter the critical
section to access CM . The mutual exclusion property therefore holds.
Note that it is possible that while a professor is in the critical section (say, to access CM ), some
professor has already "flipped" CM turn to reaccess (line 12 of Figures 8). However, the premature
flipping of CM turn cannot invalidate the algorithm's mutual exclusion property because the entering
of the critical section to reaccess CM does not depend on the value of CM turn, but rather on the value
of CM access count : as long as some professor is in the critical section to access CM , CM access count
remains greater than 0, and so no professor can exit the while-loop of Figures 9 (lines 2-6) to reaccess
CM .
The algorithm is also deadlock-free. To see this, consider an arbitrary time instance at which
A ' prof :M is the set of professors wishing to access CM and R ' prof :M is the set of professors
wishing to reaccess CM definition). Consider now the plight of some p 2 A (similar
reasoning applies in the case of reaccess). If obviously, p will succeed. Otherwise what
happens next depends on the value of CM turn: If CM turn = access then each professor in R must
undo its increment of CM reaccess count , and wait in line 5 of Figure 9 until CM turn is flipped
to reaccess . When CM reaccess count has been reset to zero, p can then enter the critical section.
Conversely, if CM turn = reaccess , then p and the other professors in A must undo their increments
of CM access count , collectively resetting the value of this variable to zero, and wait in line 5 of

Figure

8 until the professors in R enter the critical section and then flip CM turn to access .
Moreover, the algorithm permits concurrent access (and concurrent reaccess, too), meaning that
if a professor p 1 attempts to access CM while some other professor p 2 is accessing the counter, then
may succeed even if there is already a third professor waiting for reaccess to CM . This is because
is in the critical section while CM turn = access , then all professors waiting for reaccess to
CM are blocked at line 5 of Figure 9, and CM reaccess count = 0. So p 1 can immediately enter the
critical section.
Note that allowing subsequent professors to concurrently access a counter cannot indefinitely
delay a professor waiting for reaccess to the same counter because (1) the number of professors in a
committee is finite, and (2) a professor p's access to CM must be followed by a reaccess to the same
counter (unless p's access leads to a committee meeting; and if this is the case, then the professor
must enter state E to wait for the other members to finish their reaccesses so that they can start a
meeting). By assumption A1 the time between the access and reaccess, i.e., the ffi-interval, must be
long enough for other professors to finish their accesses.
Note further that permitting concurrent accesses is highly desirable because it increases the
likelihood of establishing committee meetings. For example, suppose that two sets of professors are
waiting for access and reaccess to CM , respectively, while some professor is already accessing the
counter. Deferring the reaccesses until all accesses have proceeded can only help the members of M
reach consensus, while scheduling the accesses and reaccesses in a fair manner (e.g., alternatively)
adds no help at all to the establishment of M 's meeting.
Conclusions
We have presented Multi, a new randomized algorithm for scheduling multiparty interactions. We
have shown that by properly setting the value of ffi (the amount of time a process is willing to wait
for an interaction to be established), our algorithm is both weak and strong interaction fair with
probability 1. Our results hold even if the time it takes to access a shared variable (the communication
delay) is nonnegligible. To our knowledge, this makes Multi the first algorithm for strong interaction
fairness to appear in the literature.
Strong interaction fairness has been proven impossible by any deterministic algorithm. Our results
therefore indicate that randomization is a feasible and efficient countermeasure to such impossibility
phenomena. Furthermore, since most known fairness notions are weaker than strong interaction
fairness, they too can be implemented via randomization. For example, strong process fairness [1],
where a process infinitely often ready for an enabled interaction shall participate in an interaction
infinitely often, is also realized by our randomized algorithm in spite of the fact that it cannot be
implemented by any deterministic multiparty interaction scheduling [19, 9].
Multi is an extension of Francez and Rodeh's randomized algorithm for CSP-like biparty inter-
actions. Francez and Rodeh were able to claim only weak interaction fairness for their algorithm,
and then only under the limiting assumption that the communication time is negligible compared to
ffi. In this case, strong interaction fairness would be possible even in a deterministic setting.
We have also analyzed the time complexity of our algorithm. Like Reif and Spirakis's real-time
algorithm [17], the expected time taken by Multi to establish an interaction is a constant not
depending on the total number of processes in the system.
Although Multi is presented in a shared-memory model, it can be easily converted to a message-passing
algorithm by letting some processes maintain the shared variables, and other processes
communicate with them by message passing to obtain the values of these variables. The time to
read/write a shared variable then accounts for the time it takes to deliver a message. The ffi parameter
in Assumption A1 can be properly adjusted to reflect the new communication delay so that both
weak and strong interaction fairness notions can still be guaranteed with probability 1.
Multi, as originally described in Section 3, uses an operation TEST&OP for processes to access
a shared counter atomically. This operation is rather complex and will not be generally available.
Moreover, it unnecessarily eliminates potential concurrency. So, in Section 4.4, we have proposed an
implementation of TEST&OP that uses the more basic atomic instructions inc, dec, load , and store.
Implementing Multi on a machine that does not support the atomic execution of these instructions,
as could well be the case for inc and dec, is an interesting open problem.
As discussed in Section 4.4, the implementation of TEST&OP would be much simpler if a general-purpose
mutual exclusion algorithm was used instead. However, we know of no mutual exclusion
algorithm that allows concurrent accesses to the critical section if the accesses themselves do not
conflict with one another. Therefore we had to design our own solution.
Finally, unlike deterministic algorithms, randomized algorithms such as Multi only "guarantee"
average-case behavior, not a worst-case bound. It would therefore be interesting to conduct simulation
studies on Multi to measure its response time in practical settings. Experiments in which the
size of S max and C max (see Section 4.3) vary from small constants to large values approaching the
number of professors in the system would be especially insightful.

Acknowledgments

. We would like to thank the anonymous referees for their careful reading of
the manuscript and their valuable comments.



--R

Appraising fairness in languages for distributed program- ming
On fairness as an abstraction for the design of distributed systems.
Fairness and hyperfairness in multi-party interactions
Process synchronization: Design and performance evaluation of distributed algo- rithms
A Foundation of Parallel Program Design.
A Course in Probability Theory.
Interacting Processes: A Multiparty Approach to Coordinated Distributed Programming.
A distributed abstract data type implemented by a probabilistic communication scheme.
Characterizing fairness implementability for multiparty interaction.
Coordinating first-order multiparty interactions
A comprehensive study of the complexity of multiparty interaction.
An implementation of N-party synchronization using tokens
On the advantage of free choice: A symmetric and fully distributed solution to the dining philosophers problem (extended abstract).
A distributed synchronization scheme for fair multi-process handshakes
A new and efficient implementation of multiprocess synchronization.
Algorithms for Mutual Exclusion.
Real time synchronization of interprocess communications.
Distributed algorithms for ensuring fair interprocess communications.
Some impossibility results in interprocess synchronization.

--TR

--CTR
Catuscia Palamidessi , Oltea Mihaela Herescu, A randomized encoding of the -calculus with mixed choice, Theoretical Computer Science, v.335 n.2-3, p.373-404, 23 May 2005
Rafael Corchuelo , Jos A. Prez , Antonio Ruiz-Corts, Aspect-oriented interaction in multi-organisational web-based systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.4, p.385-406, 15 March
multiparty interaction;weak interaction fairness;randomized algorithms;committee coordination;distributed algorithms;strong interaction fairness