Localizing Failures in Distributed Synchronization.
AbstractThe fault-tolerance of distributed algorithms is investigated in asynchronous message passing systems with undetectable process failures. Two specific synchronization problems are considered, the dining philosophers problem and the binary committee coordination problem. The abstraction of a bounded doorway is introduced as a general mechanism for achieving individual progress and good failure locality. Using it as a building block, optimal fault-tolerant algorithms are constructed for the two problems.
Introduction
The ability to tolerate failures is an important design requirement of computer systems in general, and
of distributed systems in particular as the detection of failures becomes difficult in such systems. We
investigate the effects of failures on distributed synchronization problems that require the co-operation
of a set of independent processes. The specific problems we study assume an underlying undirected
graph that defines the neighborhood of the processes. Inter-process communication is through message-passing
and is only possible between neighboring processes. The goal is to design solutions for which
the effect of the failure of a process can be confined to its immediate neighborhood. In other words,
we are interested in solutions where processes are shielded from the effects of non-local failures. We
assume the fail-stop model in which failures are undetectable and failed processes are indistinguishable
from processes that are very slow.
We choose the problems of dining philosophers and committee coordination as representatives of
the class of distributed synchronization problems. The dining philosophers problem is a generalization
of the mutual exclusion problem and can be used to solve many other synchronization problems. The
committee coordination problem occurs in languages such as CSP [4] and Ada [1] that are based
on synchronous message communication. We use failure locality [6] to measure the degree of fault-
tolerance. The failure locality of an algorithm denotes the size of the neighborhood that gets affected
by a failure. Thus, if an algorithm has a failure locality of m then any process for which there are no
failures within a distance of m in the underlying graph executes as if no failures occurred. In other
words, any such process continues to meet the specified safety and progress properties.
The main contribution of this paper is the presentation of tight lower bounds on the failure locality
of solutions to the dining philosophers and the committee coordination problem. This is achieved
through the presentation of lower bounds and the design of solutions that achieve them. As a part
of the optimal algorithms, we also introduce the idea of a bounded doorway . This doorway has the
interesting property that when coupled with an algorithm ensuring the absence of global starvation, the
doorway ensures the absence of local starvation without adding to the failure locality of the algorithm.
This is in contrast to other kind of doorways [6, 13] that add to the failure locality of the underlying
algorithm.
The rest of the paper is organized as follows. In Section 2 we present some of the relevant back-
ground. In Section 3, we introduce the idea of bounded doorways. In Section 4, we solve the dining
philosophers problem with an optimal failure locality. In Section 5, we solve the committee coordination
problem again with an optimal failure locality. A brief discussion appears in Section 6 and an
appendix contains the proofs of some theorems used in the main body of the paper.
Relevant Background
Locality of distributed computation has been studied by many authors [2, 14, 19, 20]. Linial [14]
considered the problem of computing functions that do not require global communication. To compute
a function, each process starts with some local data. During the computation, information is exchanged
between neighboring processes. Finally, each of the processes terminates and returns a value. A
function is said to be computed locally [2] if it can be computed in a time less than the diameter of
the network. Some of these functions include finding a maximal independent set [2, 11, 14, 15] or
computing nodes and edge colorings of a network [2, 10]. In this paper, we investigate the locality of
distributed synchronization problems that do not require processes to terminate and return results. In
particular, we concentrate on the dining philosophers problem [8, 16] and the committee coordination
problem [5].
The dining philosophers problem consists of a set of processes and a set of resources that are modeled
by a conflict graph. Each process is mapped to a node of the conflict graph and each resource is mapped
to an edge. Many solutions to the dining philosophers problem appear in the literature [3, 5, 6, 16, 20].
Styer and Peterson [20] are perhaps the first to consider the issue of locality for this problem. They
measure the locality of an algorithm by the length of the longest waiting chain of processes that may
be formed in the system. We formalize this idea of waiting chains to the notion of failure locality . For
the dining philosophers problem, failure locality of an algorithm is defined as the smallest number m
such that any process, for which there are no failures within a distance of m in the conflict graph,
is free from starvation. The algorithms obtained by Styer and Peterson achieve a failure locality of
3. Recently, we considered the problem of achieving a good failure locality in conjunction with the
problem of achieving a good response time and a good message complexity [6]. We presented solutions
that achieved a failure locality of 4 while maintaining a quadratic (in the degree of the conflict graph)
response time and a quadratic message complexity. The paper also contains an algorithm that achieves
a failure locality of 3. However, the question of the best achievable failure locality remained open.
The committee coordination problem consists of a set of interactions (or committees) and a set of
processes. The problem initially arose out of rendezvous-based communication in languages like CSP
and Ada [1, 4] where a subset of processes needs to exchange information in a synchronous manner. A
conflict graph can be constructed for this problem by mapping each interaction to a node and placing
an edge between interactions that share a common process. We concentrate on the binary version of
the problem in which every interaction has two members. Both the binary and the general versions of
the problem have been solved by many researchers [4, 5, 6, 12, 18, 19]. Sistla [19] calls a solution to
the problem to be real time if its complexity is independent of the size of the communication network.
He also investigates the formation of waiting chains and then uses this to derive a lower bound on the
response time. We define the failure locality of solutions to the committee coordination problem to be
the smallest number m such that any continuously ready interaction, for which there are no failures
within a distance of m in the conflict graph, will be eventually committed. Recently, we presented
solutions to the committee coordination problem with a failure locality of 2 [6]. But, once more the
question of the optimal failure locality remained open.
3 Bounded Doorways
Solutions to problems requiring the absence of local starvation are often composed of two parts [6,
13, 20]. The first part satisfies all the requirements of the problem except that it ensures the absence
of global starvation (i.e., no deadlocks). The second part of the solution, usually called a doorway ,
translates the absence of global starvation of the underlying solution into the absence of local starvation
(i.e., progress with respect to each process) for the composite solution. In other words, a doorway D
takes a program F ensuring the absence of global starvation, and produces a composite program
consisting of F and D such that local starvation does not occur.
Various kinds of doorways have been defined and used in the literature. A basic kind called the
first-come-first-served doorway was defined and used by Lamport in [13] in the context of the mutual
exclusion problem. This doorway consists of a finite sequence of non-waiting statements and enforces
a first-come-first-served behavior. Though useful for shared variable systems, this doorway cannot
be used for message based systems as the doorway would have to consist of waiting statements in
order to enforce a first-come-first-served behavior. A variant of this doorway was used by Styer and
Peterson to solve the dining philosophers problem in a message based model similar to ours [20]. In
their scheme neighboring processes executes a P operation on a common semaphore (implemented
by passing messages) while entering the doorway and a V operation while exiting the doorway. Two
other kinds of doorways called single doorway and double doorway were introduced in [6] in order to
avoid unbounded overtaking. All the above doorways require processes outside the doorway to wait
for processes inside the doorway and this increases the failure locality of the composite solution by at
least one.
In this paper, we introduce a new kind of a doorway that does not increase the failure locality
of the underlying computation. This doorway, referred to as a bounded doorway , is implemented by
dynamically assigning a set of distinct IDs to the processes. The IDs are distinct and used for resolving
conflicts that occur during the execution of the algorithm. We assume that the underlying solution
resolves conflicts in favor of the process with a smaller ID. In the doorway algorithm, a process that has
just made some progress selects a neighbor with a higher ID to perform an ID exchange. This exchange
results in the neighbor having a smaller ID (i.e. higher priority) than before. An ID exchange involves
sending an exchg message to the selected neighbor, waiting for an acknowledgement to be returned,
and a broadcast of the new ID to other processes. The process receiving an exchg message agrees to
the exchange of IDs only if this will lead to a smaller ID and the process is not currently participating
in another exchange. Each process maintains a queue of neighbors and chooses the candidate process
for ID exchange by scanning the queue for a process with a higher ID. (No exchange is needed if all
neighbors have a lower ID.) In order to ensure fairness, the process so chosen is placed at the end of
the queue after the exchange of IDs. Thus, a process that makes progress infinitely often while its
neighbors are starving will eventually have a higher ID (and consequently a lower priority) than all its
neighbors. This will allow the neighbors to make progress and avoid starvation.
4 The Dining Philosophers Problem
4.1 Problem Description
The problem consists of a number of processes each of which may be in one of three states: thinking,
hungry, or eating. Predicate thinking i
denotes that process i is thinking. Predicates hungry i
and
eating i
are defined similarly. Initially every process is thinking. A thinking process becomes hungry
when it needs to access the resources on the adjoining edges. A process stays hungry until it is
allowed to eat by the dining philosophers algorithm. A process accesses the resources during its eating
period, which is assumed to be finite. After that an eating process transits to the thinking state. A
dining philosophers algorithm should satisfy two requirements: mutual exclusion which requires that
neighboring processes do not eat at the same time and no starvation which requires that every hungry
process eventually gets a chance to eat.
A process may fail at any time during a computation. The failure of a process i is modeled by an
auxiliary predicate failed i
. This predicate is initially false and is set to true by the failure of process i.
Once it is true, it remains true forever. We assume the fail-stop mode of failures in which the failure
of a process is undetectable. In particular, this implies that the predicate failed i
cannot be used in
the code of an algorithm. (The predicate can however be used in the proofs of correctness.) As stated
earlier, we measure the fault-tolerance of an algorithm by its failure locality. Formally, the failure
locality of an algorithm is defined as the smallest number m such that any process, for which there
are no failures within a distance of m in the conflict graph, is free from starvation. We require that
failures have no effect on the safety properties (such as mutual exclusion) of an algorithm.
For example, consider the conflict graph of 7 processes shown in Figure 1. If the failure locality of
an algorithm is at most 1 then failures do not have any effect on the progress of processes outside the
immediate neighborhood of the failed process. In other words, the failure of process 1 can only starve
processes 2,3, and 4, the failure of process 4 can only starve processes 1,2,3,5, and 6, and so on. If an
algorithm has a failure locality of 2 then the failure of process 1 cannot starve process 7 and vice-versa.
Figure

1: Example of a Conflict Graph
4.2 Impossibility Result
It is easy to see that the a failure locality of 0 (i.e., the failure of a process does not starve any other
processes) is unachievable. This is because a process may fail while eating and that means that the
immediate neighbors, unaware of this failure, may starve. The following theorem states that a failure
locality of 1 is also unachievable.
Theorem 1 There does not exist a solution to the dining philosophers problem with a failure locality
of 1.
Proof: Suppose there exists a solution with a failure locality of one. Consider the problem instance
of 3 processes are neighbors of j but i and k are not neighbors. Consider the
following execution history in which none of the processes fail.
Initially all the processes are thinking. Process i becomes hungry first. Since thinking processes
may remain thinking forever, there exists a future state at which i starts eating while j and k are still
thinking. Now, assume that while i is eating both j and k become hungry. It is possible that process
undetectably while eating and therefore in order to ensure a failure locality of one, process k
should be allowed to eat. Thus, there exists a future state at which i and k are eating and j is hungry.
Now, suppose that i finishes eating and becomes hungry again. By the same argument as before, there
exists a future state at which k remains eating, j remains hungry, and i starts eating. Now, let process
stop eating and become hungry again. This leads us back to a state that had existed earlier in the
history: process i is eating and processes j and k are hungry. Note that process j remains hungry in
all the intermediate states. This scenario may repeat continuously, giving us the desired contradiction
as process j remains hungry forever though none of its neighbors have failed. 2
Initially: /* The main procedure */
ack i
processes in N i
in any order) - wait until ack i
pending i
wait until all-forks i
all-forks
all-low-forks i
release
release-high
forever

Figure

2: Algorithm for Process i
4.3 An Optimal Algorithm
We now construct an optimal algorithm with a failure locality of 2. The algorithm consists of two parts:
a bounded doorway as discussed in Section 3, and a scheme to ensure mutual exclusion and absence
of global starvation. Mutual exclusion is ensured by associating forks with edges and maintaining the
invariant that an eating process has all the neighboring forks. In order to ensure the absence of global
starvation, conflicting requests to the same fork are resolved in favor of the process with the smaller
ID. Since this may lead to the formation of long waiting chains (which in turn results in poor failure
locality), processes break such long chains by selectively releasing forks. However, the process with the
smallest ID does not release any forks. This ensures the absence of global starvation. The ID exchange
mechanism due to the bounded doorway ensures that a continuously hungry process will eventually
have a smaller ID than its competing neighbors and will be able to eat. The composite algorithm thus
also ensures freedom from local starvation.
The algorithm is shown in figures 2 and 3. For any process i, the set N i
defines its neighbors. Given
a process j 2 N i
with
, we refer to process j as a high neighbor of process i and refer to
process i as a low neighbor of process j. Similarly, the fork between the processes is referred to as
a high fork at process i and as a low fork at process j. Process i uses a number of local variables.
refers to the ID of process i and variable ID ij
refers to the ID of process j as known at
process i. Boolean fork ij
is true iff the fork between processes i and j is at process i. Initially the
fork is at the process with the smaller ID. The presence of a process inside the bounded doorway is
indicated by a variable ack i
. This variable is false iff process i is executing the code of the bounded
doorway, i.e., exchanging its ID with a neighbor. A queue Q i
is used in order to select the next process
On receiving message hrequesti
from j such that ID ij
pending i
On receiving message hrequesti
from j such that ID ij
pending i
release-high-forks fi
On receiving message hfork, flagi from j:
requested ij
if f lag then pending i
if all-low-forks i
then request-high-forks
lag
On receiving message hexchg, IDi from j:
if (ack i
send hexchg-yes, ID i i to j;
for each (k 2 N i
do
send hnewid, IDi to k od
if (all-low-forks i - hungry i
request-high-forks fi
else send hexchg-noi to j fi
On receiving message hexchg-yes, IDi from j:
for each (k 2 N i
do
send hnewid, IDi to k od
ack i
true
On receiving message hexchg-noi from j:
ack i
true
On receiving message hnewid,IDi from j:
Procedure request-forks
for each j 2 N i
do
then
send hrequest i to j;
requested ij
:= true fi od
Procedure request-high-forks
for each (j 2 N i
do
then
send hrequest i to j;
requested ij
:= true fi od
Procedure release-forks
for each (j 2 pending i
do
od
release-forks
Procedure release-high-forks
for each (j 2 pending i
od
release-high-forks
Procedure release-id
ack i
send hexchg, ID i
i to j fi
Procedure send-fork(j)
pending i
pending
send hfork; truei to j;
requested ij
true
else send hfork; falsei to j fi

Figure

3: Algorithm for process i (continued)
for exchanging IDs. Initially ack i
is true and Q i
is set to any arbitrary ordering of the processes in N i
requested ij is true iff process i has sent an outstanding fork request to process j. Set pending i
contains the fork requests that have not yet been serviced.
When a process becomes hungry, it attempts to collect missing forks by sending request messages,
as in procedure request-forks, to the neighbors. A process i receiving a request for a fork decides
whether it is going to release the fork to requester j depending on its state and the relative order of
the IDs. If ID ij
then the fork is released if process i is thinking or if it has not collected all
the low forks (this condition is captured by the predicate release-high i
then the fork is
released (along with all captured high forks in order to avoid the formation of long waiting chains) if
process i is thinking or if it has not collected all the forks (this condition is captured by the predicate
release i
). Note from procedure send-fork that if the process releasing a fork is hungry then it informs
the requesting process of this by setting a flag in the fork to true. If a fork is not released to a requesting
process then the ID of the requester is saved in set pending i
for future consideration.
If the reception of the fork completes the collection of all the low forks at a process then request for
missing high forks are made by calling procedure request-high-forks. Otherwise, if the fork just received
is a high fork with a true flag then the fork is returned to the sender.
Once a process gathers all its forks, it transits to the eating state and enters the critical section.
Upon exiting from the critical section, it sets its state to thinking, releases all the forks in pending,
and executes the bounded doorway code, i.e., procedure release-id, in order to exchange IDs. In this
procedure, process i first invokes a function next to choose the next process with a higher ID from
the queue Q i
. If such a process exists then its ID is returned and it is moved to the end of the queue
, otherwise a special value null is returned. The implementation of the function is straightforward
and not shown here. If function next returns a non-null value j then ack i
is set to false and an exchg
message is sent to process j. Upon receiving this message, process j participates in an ID exchange iff
it is outside the doorway (indicated by ack being true) and the ID exchange will lower its ID. In that
case process j sends an exchg-yes message to i and also informs all neighbors of the new ID. Otherwise,
process j responds with an exchg-no message to process i. Upon receiving a positive acknowledgement
from process j, process i completes the ID exchange process and informs all of its neighbors of the new
ID. If a negative acknowledgement is received then no exchange is carried out. In either case, ack i
is
set to true and the next iteration of state transitions begins.
4.4 Proof of Correctness
We use the temporal operators 2 and 3 [17] in the following proof. Briefly, 2p means that the formula
p holds at all states in the history beginning with the current state, and 3p means that the formula p
holds at some future state in the history beginning with the current state. The following two lemmas
are proved in the appendix.
Lemma 1 If a non-failed process i starves then eventually for every neighbor j, the ordering of ID i
and ID j becomes fixed. Formally,
2(2(:failed
)i).
Lemma 2 If a non-failed process i starves then eventually any low neighbor j either fails, or remains
non-eating forever with ID ji
2(2(:failed i
(failed j
(:eating j
)))i).
We construct a waiting graph W i
for any starving non-failed process i as follows:
Process i is in W i .
ffl For any process j in W i
apply Lemma 2. Add a neighbor k to W i
for which
:failed k
holds.
ffl Repeat until no more processes can be added to W i .
Informally, graph W i
includes process i and all starving non-failed processes that are reachable by a
chain of decreasing IDs through other processes in W i
. The following lemma is proved in the appendix.
Lemma 3 For any process j in W i
and any low neighbor k of j, eventually the fork between j and k
either remains at j forever or remains at k forever. Formally,
)ii.
Based on the above lemma, we can prove the following theorem about the failure locality of the
algorithm.
Theorem 2 If process i starves then there is a failed process at a distance at most 2 from it.
Proof: For the sake of contradiction, assume that process i starves and all the processes within a
distance of 2 from i do not fail. By Lemma 3, for any neighbor j of process i eventually either
holds forever. Now, there
are two cases to consider: either eventually process i is holding all its low forks forever or eventually
process i is missing some low fork forever. In the former case, process i sends requests, if necessary, to
its high neighbors to collect the high forks. Since these processes do not fail they will eventually release
the forks, and thus process i will eventually collect all the forks and start eating. This contradicts our
assumption that process i starves.
In the second case, let j be a low neighbor that holds on to a fork from process i forever. Since
process j is holding a high fork, it must have collected all its low forks. Consequently, process j can start
collecting any missing high forks. Since processes within a distance of 2 from i do not fail, processes
within a distance of 1 from j do not fail. This implies that process j will be able to collect all the high
forks and start eating. Eventually process j will finishes eating and release the fork to process i. This
contradicts the assumption that the fork shared by processes i and j stays at process j forever. 2
5 The Committee Coordination Problem
5.1 Problem Description
The problem consists of a set of processes and a set of interactions. Each process has a predetermined
set of interactions that it may participate in and each interaction has a predetermined set of processes
that co-operate to execute it. Processes that may participate in the same interaction are physically
close to each other and can communicate directly. A process may be in one of three states: idle,
ready, and commit. Predicate idle i
denotes that process i is idle. Predicates ready i
and commit i
are
defined similarly. Initially all processes are idle. From time to time, a process becomes ready to take
part in any of the interactions associated with it and it remains ready until one of the interactions
is committed. Similar to a process, an interaction may also be in one of three states: idle, ready, or
commit. An interaction is ready to be executed if all the processes associated with it are ready, an
interaction is in the commit state if all the processes participating in it are committed to perform it,
and an interaction is idle otherwise. During the execution of an interaction, the interaction and all the
processes associated with the interaction are in the state commit. The commitment of each interaction
eventually terminates, at which point the interaction and the processes become idle again.
We say that two interactions conflict with each other if they share a common process. Based on
this conflict relation between interactions, we define a conflict graph as follows: we represent each
interaction by a node and place an edge between two nodes if the corresponding interactions conflict.
As mentioned earlier, the state transitions of a process occur in the order idle to ready to commit and
back to idle. The state transitions of an interaction are similar except for the fact that an interaction
may transit to state idle directly from the state ready. This is because two neighboring interactions
may be ready at the same time and committing one changes the state of the other to idle. The time for
which an interaction is committed is assumed to be finite. A solution to the committee coordination
problem should satisfy two safety requirements, synchronization and mutual exclusion, and one progress
requirement, weak interaction fairness. Synchronization requires that the commitment of an interaction
is only started if it is ready. Mutual exclusion requires that no two interactions sharing a common
process commit simultaneously. Weak interaction fairness requires that if an interaction is continuously
ready then it will eventually be committed.
As in the dining philosophers problem, a process may fail at any time during a computation and
this is modeled by an auxiliary predicate failed i . We say that an interaction fails if any process
belonging to it fails. The failure locality of an algorithm is defined as the smallest number m such
that for any interaction, as long as interactions within a distance of m in the conflict graph do not fail,
the requirement of weak interaction fairness is satisfied. Failures do not impact the requirements of
synchronization and mutual exclusion as these are safety properties.
5.2 Impossibility Result
The following theorem shows that the effect of failure of a process cannot be limited just to the
interactions in which it participates.
Theorem 3 There does not exist a solution to the committee coordination problem that achieves a
failure locality of 0.
Proof: The proof is by reduction to the well-known result about the impossibility of distributed
consensus with one faulty process [9]. Assume that there exists an algorithm that achieves a failure
locality of 0. In other words, the algorithm supposedly ensures that as long as processes in an interaction
are ready and do not fail, the interaction or one of its neighbors commit eventually. We use such an
algorithm to solve the distributed consensus problem for three processes
In the consensus problem every process has an initial value and all non-failed processes have to
agree on a common value that was one of the initial values. For the case of three processes that we
consider here, we form three interactions I= fi; jg, J= fj; kg, and K= fk; ig and devise a mechanism
by which the commitment of an interaction (e.g. I) implies that a consensus is reached on the initial
value of the corresponding process (in this case i).
Every process first broadcasts its initial value to the other processes and then becomes ready to
participate in any interaction of which it is a member. By the requirements of synchronization, mutual
exclusion and weak interaction fairness, the underlying committee coordination algorithm commits
exactly one of the interactions I, J , or K. The processes that are participating in the committed
interaction broadcast its identity to the third process. Finally, the processes agree on the initial value
of process corresponding to the committed interaction.
Since processes broadcast their initial values before becoming ready, the value corresponding to a
committed interaction is available at all the processes. Since at most one process fails, at least one
interaction will be ready to be committed. By the assumed failure locality of the underlying committee
coordination algorithm, at least one interaction commits. Therefore, at least one process is able to
broadcast the identity of the committed interaction. As a result, all the non-failed processes agree on
a common value that was one of the initial values. 2
Initially: /* The main procedure */
ack i
processes in N i
in any order) - wait until ack i
pending i
wakeup-neighbors;
wait until commit i
hperform
state i
release-id
forever

Figure

4: Algorithm for Process i
5.3 An Optimal Algorithm
We now construct an optimal algorithm with a failure locality of 1 for the binary version of the
problem. As for the dining philosophers problem, we use a bounded doorway in which processes
exchange IDs and another piece of code that ensures the two safety properties and global progress.
For every interaction, the process with the smaller ID is designated as the manager and is responsible
for committing the interaction. A process may possibly manage several interactions based upon the
relative ordering of the IDs of the processes. For any process i, set N i
defines the set of processes that
participate in some common interaction with process i. When process i becomes ready, it attempts to
commit the interactions it manages by invoking procedure request-commitment. While executing this
procedure, process i sends request messages to each process j for which fi; jg is an interaction managed
by process i. When process j receives a request, it replies with a yes message if it is ready and has
not sent a yes message to another manager. Otherwise, it saves i in the set pending j
. A local variable
is set to true iff process j has sent a yes message to some manager. Upon receiving a yes
message from process j, process i commits the interaction fi; jg provided it is still ready and has not
responded with a yes message to some other manager. Otherwise, manager i responds with a release
message to process j. On receiving this release message, process j informs the neighboring managers
to retransmit request messages by sending a wakeup message to each process in pending j
. On receiving
a wakeup message from process j, these processes try to commit the corresponding interactions again.
The complete algorithm is shown in figures 4 and 5. Local variables ID i
ack i
are as in the dining philosophers algorithm. The implementation of the bounded doorway, i.e.,
procedure release-id, is also as in the previous solution.
On receiving message hrequesti from j:
if (ready i
send hyesi to j;
else pending i
On receiving message hyesi from j
send hcommiti to j;
state i
else send hreleasei to j fi;
requested ij
On receiving message hreleasei from j
wakeup-neighbors;
request-commitment
On receiving message hwakeupi from j
requested ij
if ready i
then
send hrequesti to j;
requested ij
:= true fi
On receiving message hexchg, IDi from j:
if (ack i - ID i
send hexchg-yes, ID i
i to j;
for each (k 2 N i
do
send hnewid, IDi to ki od
else send hexchg-noi to j fi
On receiving message hcommiti from j:
state i := commit
On receiving message hexchg-yes, IDi from j:
for each (k 2 N i
do
send hnewid, IDi to ki od
ack i
On receiving message hexchg-no, IDi from j:
ack i
On receiving message hnewid,IDi from j:
Procedure request-commitment
for each (j 2 N i
do
if :bound i
then
send hrequesti to j;
requested ij
:= true fi od
request-commitment
Procedure wakeup-neighbors
for each (j 2 pending i
do
send hwakeupi to j od
pending i
wakeup-neighbors
Procedure release-id
ack i
send hexchg, ID i i to j fi

Figure

5: Algorithm for process i (continued)
5.4 Proof of Correctness
The following two lemmas can be proved in a manner similar to Lemma 1 and Lemma 2.
Lemma 4 If a non-failed process i remains ready forever then eventually for every neighbor j, the
ordering of ID i
and ID j
becomes fixed. Formally,
2(2(:failed
Lemma 5 If a non-failed process i remains ready forever then eventually any low neighbor of i either
fails, remains non-committed forever. Formally,
2(2(:failed
(failed j
)))i).
We construct a waiting graph W i for any non-failed process i that is ready forever as
follows:
Process i is in W i .
ffl For any process j in W i
apply Lemma 5. Add a neighbor k to W i
for which
holds.
ffl Repeat until no more processes can be added to W i
Informally, graph W i
includes process i and all non-failed processes that are ready forever and
reachable by a chain of decreasing IDs through other processes in W i
. The following lemma is proved
in the appendix.
Lemma 6 For any process j in W i , eventually bound j becomes stable. Formally,
)i.
Based on the above lemma, we can prove the following theorem about the failure locality of the
algorithm.
Theorem 4 If interaction I remains ready forever then either I or some interaction conflicting with
I fails.
Proof: For the sake of contradiction, assume that interaction I remains ready forever and that all
interactions conflicting with I do not fail. Let i and j be the two processes in I. By Lemma 4, assume
without loss of generality that
belong to W i
and by Lemma 6,
eventually bound i
and bound j
become fixed. If bound j
becomes fixed to true then since neighboring
interactions of I do not fail, process j will eventually send a yes message to a non-failed process. This
process will eventually respond with a commit or a release message. In the former case, process j
becomes non-ready and in the latter case, bound j
is reset to false. Both of these are not possible by
assumption. Therefore, it must be the case that bound j
is fixed to false eventually. Similarly, it can be
shown that bound i
is fixed to false eventually. From the algorithm, process j sends a request message
to process i each time bound j
is reset to false. Consider a request message sent by process j after
becomes fixed to false. Process i responds to this message by either a yes or a wakeup message.
In the former case, process j becomes non-ready and in the latter case, process j retransmits a request
message. The former is not possible as process j remains continuously ready. Therefore, process j
sends a request message to process i infinitely often. Since bound i
is eventually fixed to false, process
eventually respond with a yes message, thus committing interaction I . This contradicts our
assumption that I remains ready forever. 2
6 Concluding Remarks
In this paper we proved that a failure locality of one cannot be achieved for the dining philosophers
problem. The impossibility result was essentially based on the absence of global information in a
totally asynchronous distributed system. Subsequently, we presented an algorithm with an optimal
failure locality of two. The algorithm was based on the idea of a bounded doorway where processes
exchanged IDs with their neighbors upon making progress. After that we considered the committee
coordination problem and showed that a failure locality of 0 is unachievable for this problem. The proof
was based on a reduction to the problem of distributed consensus. Finally, we presented an optimal
algorithm for the binary version of the problem, once more based on the idea of a bounded doorway.
The general case of the committee coordination problem can be solved by a reduction to the dining
philosophers problem [5]. If we use the optimal algorithm that is presented here then the resulting
solution to the committee coordination problem has a failure locality of two. It is an open question
whether a failure locality of one can be achieved for this problem.



--R

Reference manual for the Ada programming language.
Network decomposition and locality in distributed computation.
A dining philosophers algorithm with polynomial response time.
An effective implementation for the generalized input-output construct of CSP
Parallel Program Design: A Foundation.
Efficient fault tolerant algorithms for resource allocation in distributed systems.
Adaptive algorithms for the mutual exclusion problem.
Hierarchical ordering of sequential processes.
Impossibility of distributed consensus with one faulty process.
Parallel (ffi
A fast parallel algorithm for the maximal independent set problem.
An algorithm for N-party synchronization using tokens
The mutual exclusion problem: Part I and II.
Distributive algorithms - global solutions from local data
A simple parallel algorithm for the maximal independent set problem.
Fast allocation of nearby resources in a distributed system.
How to Cook a Temporal Proof System for Your Pet Language
A new and efficient implementation of multiprocess synchronization.
Distributed algorithms for ensuring fair interprocess communications.
Improved algorithms for distributed resource allocation.
--TR

--CTR
Hagit Attiya , Eyal Dagan, Improved implementations of binary universal operations, Journal of the ACM (JACM), v.48 n.5, p.1013-1037, September 2001
Yehuda Afek , Michael Merritt , Gadi Taubenfeld , Dan Touitou, Disentangling multi-object operations (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.111-120, August 21-24, 1997, Santa Barbara, California, United States
concurrency;fault-tolerance;lower bounds;distributed algorithms;synchronization