The complexity of synchronous iterative Do-All with crashes.
The ability to cooperate on common tasks in a distributed setting is key to solving a broad range of computation problems ranging from distributed search such as SETI to distributed simulation and multi-agent collaboration. Do-All, an abstraction of such cooperative activity, is the problem of performing N tasks in a distributed system of P failure-prone processors. Many distributed and parallel algorithms have been developed for this problem and several algorithm simulations have been developed by iterating Do-All algorithms. The efficiency of the solutions for Do-All is measured in terms of work complexity where all processing steps taken by all processors are counted. Work is ideally expressed as a function of N, P, and f, the number of processor crashes. However the known lower bounds and the upper bounds for extant algorithms do not adequately show how work depends on f. We present the first non-trivial lower bounds for Do-All that capture the dependence of work on N, P and f. For the model of computation where processors are able to make perfect load-balancing decisions locally, we also present matching upper bounds. We define the r-iterative Do-All problem that abstracts facts the repeated use of Do-All such as found in typical algorithm simulations. Our f-sensitive analysis enables us to derive tight bounds for r-iterative Do-All work (that are stronger than the r-fold work complexity of a single Do-All). Our approach that models perfect load-balancing allows for the analysis of specific algorithms to be divided into two parts: (i) the analysis of the cost of tolerating failures while performing work under "free" load-balancing, and (ii) the analysis of the cost of implementing load-balancing. We demonstrate the utility and generality of this approach by improving the analysis of two known efficient algorithms. We give an improved analysis of an efficient message-passing algorithm. We also derive a tight and complete analysis of the best known Do-All algorithm for the synchronous shared-memory model. Finally we present a new upper bound on simulations of synchronous shared-memory algorithms on crash-prone processors.
Introduction
Performing a set of tasks in a decentralized setting is a fundamental problem in distributed comput-
ing. This is often challenging because the set of processors available to the computation and their
ability to communicate may dynamically change due to perturbations in the computation medium.
An abstract statement of this problem, referred to as the Do-All problem | P fault-prone processors
perform N independent tasks | is one of the standard problems in the research on the complexity
of fault-tolerant distributed computation [9, 18]. This problem has been studied in a variety of set-
tings, e.g., in shared-memory models (Write-All) [19, 20, 26], in message-passing models [7, 9, 11],
and in partitionable networks (Omni-Do) [8, 15, 25]. Solutions for Do-All must perform all tasks
e-ciently in the presence of specic failure patterns. The e-ciency is assessed in terms of work,
time and communication complexity depending on the specic model of computation.
In the design of practical distributed/parallel programs one needs to ensure good performance
and dependability under unpredictable load patterns caused, for example by deviations from synchrony
or by the failures of some processors to complete tasks on time. Here again, a common
challenge is to perform N independent tasks on P processors [14]. Such tasks could be copying a
large array, searching a collection of data, or applying a function to all elements of a matrix [12, 13].
Other examples include checking all the points in a large solution space, trying to generate a witness
or to refute its existence, or simply performing a number of similar independent calculations.
In this paper we focus on the work complexity of the Do-All problem in the presence of arbitrary
failure patterns imposed by an adversary. The processors are synchronous and are assumed
to be fail-stop [31]. The work complexity re
ects the amount of processing steps expended by
an algorithm in solving the problem and this incorporates the total number of tasks, including
multiplicities, performed by the algorithm. A distinguishing feature of our new results is that the
complexity is expressed in terms of the number of processor crashes f in addition to the number
of processors P and the size of the problem N .
Our approach is motivated in part by the analyses of the consensus problems. The venerable
FLP impossibility result [10] and the algorithms that solve consensus in the models that allow fault-tolerant
solutions teach the following: (i) asynchronous models are too weak for fault-tolerance [23],
and (ii) the maximum number of processor failures needs to be included in upper/lower bounds
and impossibility results, e.g., to tolerate f failures in some models, consensus algorithms require
processors [24, 29]. In this work we consider crash failures to ensure that solutions
exist for as long as the number of failures f is inferior to the number of processors P , and we aim
to express the work of the synchronous processors as a function of N , P and f .
Until very recently, an unsatisfactory landscape existed with respect to the understanding of
how the upper and lower bounds on work depend on f , the number of failures. That is, work was
typically given as a function of N and P , but it was either not elucidated how f impacts work,
or, when f was a part of the equation, it was primarily due to the nature of a specic algorithm,
and not due to the inherent properties of the Do-All problem. For example, the work of the best
known synchronous shared-memory algorithm [18] is given solely as the function of N and P . This
is also the case with the best known asynchronous shared-memory algorithm [3]. Similarly, the best
known shared-memory lower bound on work for Do-All is not parameterized in terms of f [20],
however it is shown that for any shared-memory algorithm will have to take at least log P time
steps. Likewise, the best known lower bound applicable to message-passing models does not involve
f [4]. The work of message-passing algorithms, e.g. [7, 11], typically includes f , but this is due
to the use of single coordinators, which means that for f coordinator failures the work necessarily
includes a factor f  P . A message-passing algorithm using multiple coordinators [5] avoids this
ine-ciency and includes a factor that depends on log f (but as we show in this paper, that analysis
involves f in a somewhat supercial way). Thus prior lower/upper bound results for Do-All do not
teach adequately how the work complexity depends on the number of failures f .
When considering the synchronous shared-memory computing with failure-prone processors the
impact of imprecise analysis of work complexity is especially signicant. Approaches such as [22, 30]
use iterative Do-All approach to execute synchronous parallel (pram) algorithms on failure-prone
processors by simulating the parallel steps of ideal processors with the help of some chosen DoAll
algorithm (see also related work below). In particular it was shown that the execution of a
single N-processor step on P failure-prone processors does not exceed the asymptotic complexity
of solving a N-size instance of the Do-All problem using P failure-prone processors. Thus if WN;P
is the complexity of solving a Do-All instance of size N using P processors, and the parallel-
timeprocessor product of the given N-processor algorithm is   N , then the algorithm can be
deterministically simulated with work O(  WN;P ). If the analysis does not accurately re
ect the
impact of the number of failures f , then the resulting upper bound is needlessly in
ated.
Contributions. In this work we study the work complexity of deterministic Do-All in the presence
of arbitrary dynamic patterns of stop-failures. Let N be the size of the Do-All problem,
P the number of processors, and f the number of crashes (0  f < P  N ). We present the
rst complete analysis of Do-All work complexity under the perfect load balancing assumption by
proving matching upper and lower bounds as functions of N , P and f . This is for the model of
computation where the computation is fully abstracted away from the low-level shared-memory
and message-passing issues, and where a worst-case omniscient dynamic adversary can cause up to
f crashes. This also establishes the rst non-trivial lower bound for Do-All for moderate number
of failures (f  P= log P ). An important contribution of this work is the denition and analysis of
the r-iterative Do-All problem that models the repetitive use of Do-All algorithms (such as found
in algorithm simulations).
We demonstrate the utility and generality of our results by showing new bounds on work for
fault-tolerant simulations of arbitrary pram algorithms on crash-prone processors, and by improving
the analysis of two known e-cient algorithms. We derive a new and complete failure sensitivity
analysis of the best known algorithm for the synchronous shared-memory model (algorithm W [18]).
We also give an improved analysis of an e-cient message-passing algorithm (algorithm AN [5]).
We let Do-All(N; stand for the Do-All problem for N tasks, P processors and up to f
failures. We let Do-All O (N; f) denote the Do-All(N; problem that is solved with the use
of an omniscient oracle that assists the processors (but unlike the oracle's delphian colleague, it
cannot predict the future). The oracle assumption is used as a tool for studying the work complexity
patterns of any fault-tolerant algorithm that implements perfect work-load balancing. This allows
for the complexity analysis of specic algorithms to be divided into two parts: (i) the analysis of
the cost of tolerating failures while performing work assuming perfect load-balancing, and (ii) the
analysis of the cost of implementing perfect load-balancing. We use exactly this approach to derive
new f-sensitive upper bounds for message-passing and shared-memory models.
We have recently shown [16], building on prior results [19], that Do-All O (N; f) can be solved
with work O(N+P log P
log log P ) where f < P , and gave a matching lower bound in the specic case where
log log P
(log log P This meant that as long as the adversary can cause at least P
log log P
failures, Do-All O (N; P; f) has matching upper and lower bounds of N +P log P
log log P
. We also showed
that when
log P ) then Do-All O (N; f) can be solved with work O(N
Thus prior to our newest results: (i) no non-trivial lower bounds were known for f < P
log P ,
(ii) no f-sensitive analysis was available for the upper bounds when f is between P
log P and P
log log P ,
and therefore, (iii) there existed a gap in upper/lower bounds analysis for the range 1 < f < P
log log P ,
practical concerns would be well served by the knowledge of what happens in
Do-All when the number of failures is moderate. In particular, it is important to understand the
behavior of the best known algorithms for the entire range of f .
The detailed contributions in this work are as follows.
I. We provide upper bounds (Section 3.1) and matching lower bounds (Section 3.2) that address
all remaining gaps, hence we give a complete analysis of Do-All O (N; f) for the entire range
of f . The bounds on work W are: 1
(a)
log log P
log c > 0;
f
when f  c P
log c > 0:
(1)
The lower bounds of course apply to algorithms in weaker models.
It turns out that the quantity Q P;f , dened below and extracted from the bounds
plays an important role in the analysis of complexity of several algorithms.
log P
log log P when f > c P
log c > 0;
f
log c > 0:
(2)
We use our bounds (1) to derive new bounds for algorithms where the extant analyses do not
integrate f adequately. This is done by analyzing how the work-load balancing is implemented by
the algorithms, e.g., by using coordinators or global data-structures. We show the following.
II. In Section 4.1 we provide new analysis of algorithm AN of Chlebus et al. [5] for Do-All in
the message-passing model with crashes. This algorithm has best known work for moderate
number of failures. We show the complete analysis of work W and message complexity
III. In Section 5.1 we give a complete analysis of the work complexity W of the algorithm of
Kanellakis and Shvartsman [18] that solves the Do-All (Write-All) problem in synchronous
shared-memory systems with processor crashes:
Note that these two algorithms [5, 18] are designed for dierent models and use dissimilar data and
control structures, however both algorithms make their load-balancing decisions by gathering global
knowledge. By understanding what work is expended by for load balancing vs. the inherent work
overhead due to the lower bounds (1), we are able to obtain the new results while demonstrating
the utility and the generality of our approach.
Do-All algorithms have been used in developing simulations of failure-free algorithms on failure-prone
processors, e.g., [22, 30]. This is done by iteratively using a Do-All algorithm to simulate
the steps of the failure-free processors. In this paper we abstract this idea as the iterative Do-All
problem as follows:
The r-iterative Do-All(N; is the problem of using P processors
to solve r instances of N-task Do-All by doing one set of tasks at a time.
We let
g" stand for \O" when describing an upper bound and for
" when describing a lower bound. All
logarithms are to the base 2 unless explicitly specied otherwise. The expression log X stands for maxf1; log 2 Xg
for the given X in the description of complexity results.
The oracle r-Do-All O (N; f) is dened similarly. An obvious solution for this problem is to run a
Do-All algorithm r times. If the work complexity of Do-All in a given model is WN;P;f , then the
work of r-Do-All is clearly no more than r  WN;P;f . We present a substantially better analysis:
IV. In Section 3.3 we show matching upper and lower bounds on work W for r-Do-All O (N;
where f < P  N , for specic ranges of failures.
(a)
r
log log P
log
r
log Pr
f
when f  P r
log
We extract the quantity R r;P;f , dened below, from the bounds (3)(a,b) above, as it plays an
important role in the analysis of complexity of iterative Do-All algorithms.
R r;P;f =<
log P
log log P
log
log P
log Pr
f
when f  P r
log
Note that for any r we have Q P;f  R r;P;f , and for the specic range of f in (4)(b) we have that
with respect to r (xed P and f ). Thus our bounds (3) are asymptotically better
than those obtained by computing the product of r and the (non-iterated) Do-All bounds (1).
V. In Section 4.2 we show that r-Do-All(N; f) can be solved with synchronous message-passing
processors with the following work complexity W and message complexity
r  log f
r  (N +R r;P;f )
and
VI. In Section 5.2 we use r-Do-All(N; f) to show that P processors with crashes can simulate
any synchronous N-processor, r-time shared-memory algorithm (pram) with work:
This last result is strictly better than the previous deterministic bounds for parallel algorithm
simulations using the Do-All algorithm [18] (the best known to date) and simulation techniques
such as [22, 30] (due of the the relationship between Q P;f and R r;P;f as pointed out above).
Related work|algorithm simulations. Do-All algorithms can be used iteratively to simulate
parallel algorithms formulated for synchronous failure-free processors in deterministic and probabilistic
settings [22, 20, 27, 28, 30]. This commonly requires that (i) the individual processor
steps are made idempotent (since they may have to be performed multiple times due to failures or
asynchrony), and that (ii) a linear in the number of processors auxiliary memory is made available
(to be used as a \scratchpad" and to store intermediate results). While the former can be solved
with the help of an automated tool, e.g., a compiler, the latter requires sophisticated solutions because
of the di-culty of (re)using the auxiliary memory due to \late writers" (i.e., processors that
are slow and that unknowingly write stale values to memory). Examples of randomized solutions
addressing these problems include [2, 1, 21]. Another important aspect of algorithm simulations is
the use of on optimistic approach, where the computation may proceed for several steps assuming
that all tasks assigned to active processors are successfully completed. For example, a series of
potentially incorrect tentative steps can be combined with a complete denitive step that detects
and rolls back incorrect computation steps [20] such that the overall computation is e-cient with
high probability. Note that in some deterministic models optimal simulations are possible (cf. [30]),
however randomized solutions are able to achieve optimality (whp) for broader ranges of models and
algorithms. Practical implementations are discussed in [6], where it is also observed that parallel
computation can be made faster by essentially ignoring processors that are slower than others.
The rest of the paper is structured as follows. In Section 2 we present models and denitions. In
Section 3 we present the bounds under the perfect load-balancing assumption. In Section 4 we
give new upper bounds for the message-passing model. In Section 5 we give upper bounds for the
shared-memory model and for pram simulations. We conclude in Section 6.
Models and Denitions
We dene the models, the abstract problem of performing N tasks in a distributed environment
consisting of P processors that are subject to stop-failures, and the work complexity measure.
Distributed setting. We consider a distributed system consisting of P synchronous processors.
We assume that P is xed and is known. Each processor has a unique identier (pid) and the
set of pids is totally ordered. A processor's activity is governed by a local clock. For a non-faulty
synchronous systems all processor clocks are identical. To model failures we introduce delays
between local clock ticks.
Tasks. We dene a task to be a computation that can be performed by any processor in at most
one time step; its execution does not dependent on any other task. The tasks are also idempotent ,
i.e., executing a task many times and/or concurrently has the same eect as executing the task
once. Tasks are uniquely identied by their task identiers (tids) and the set of tids is totally
ordered. We denote by T the set of N tasks and we assume that T is known to all the processors.
Model of failures. We assume the fail-stop processor model [31]. A processor may crash at
any moment during the computation and once crashed it does not restart. We let an omniscient
adversary impose failures on the system, and we use the term failure pattern to denote the set
of the events, i.e., crashes, caused by the adversary. A failure model is then the set of all failure
patterns for a given adversary. For a failure pattern F , we dene the size f of the failure pattern
as (the number of failures).
The Oracle model. In Section 3 we consider computation where processors are assisted by a
deterministic omniscient oracle. Any processor may contact the oracle once per step. The introduction
of the oracle serves two purposes.
(1) The oracle strengthens the model by providing the processors with any information about the
progress of the computation (the oracle cannot predict the future). Thus the lower bounds established
for the oracle model also apply to any weaker model, e.g., without an oracle.
(2) The oracle abstracts away any concerns about communication that normally dominate specic
message-passing and shared-memory models. This allows for the most general results to be established
and it enables us to use these results in the context of specic models by understanding how
the information provided by an oracle is simulated in specic algorithms.
Communication. In Sections 4 and 5 we deal with message-passing and shared-memory models.
For computation in the message-passing model, we assume that there is a known upper bound on
message delays. (Communication complexity is dened in Section 4.) When considering computation
in the shared-memory model, we assume that reading or writing to a memory cell takes one
time unit, and that reads and writes can be concurrent.
Do-All problems. We dene the Do-All problem as follows:
Do-All: Given a set T of N tasks and P processors, perform all tasks for any failure
pattern in the failure model F .
We let Do-All(N; stand for the Do-All problem for N tasks, P processors (P  N ), and any
pattern of crashes F such that jF j  f < P . We let Do-All O (N; stand for the Do-All(N;
problem with the oracle. We dene the iterative Do-All problem as follows:
Iterative Do-All: Given any r sets T r of N tasks each and P processors, perform
all r  N tasks, doing one set at a time, for any failure pattern in the failure model F .
We denote such r-iterative Do-All by r-Do-All(N; The oracle version r-Do-All O (N; f) is
dened similarly.
Measuring e-ciency. We are interested in studying the complexity of Do-All measured as work
(cf. [18, 9, 7]). We assume that it takes a unit of time for a processor to perform a unit of work,
and that a single task corresponds to a unit of work. Our denition of work complexity is based
on the available processor steps measure [19]. Let F be the adversary model. For a computation
subject to a failure pattern F , F 2 F , denote by P i the number of processors completing a unit
of work in step i of the computation.
Denition 2.1 Given a problem of size N and a P -processor algorithm that solves the problem in
the failure model F , if the algorithm solves the problem for a pattern F in F , with jF j  f , by time
step  , then the work complexity W of the algorithm is:
Note that the idling processors still consume a unit of work per step even though they do not
contribute to the computation. Denition 2.1 does not depend on the specics of the low-level
target model of computation, e.g., whether it is message-passing or shared-memory. (We will give
a similar denition for communication complexity in Section 4.)
3 The Bounds with Perfect Load Balancing
In this section we give the complete analysis of the upper and lower bounds for the Do-All O (N;
and r-Do-All O (N; problems for the entire range of f crashes (f < P  N ). (Note: we use the
quantities Q P;f and R r;P;f that are dened in Section 1 in equations (2) and (4) respectively.)
3.1 Do-All Upper Bounds
To study the upper bounds for Do-All we give an oracle-based algorithm in Figure 1. The oracle
tells each processor whether or not all tasks have been performed Oracle-says(), and what task to
perform next Oracle-task() (the correctness of the algorithm is trivial). Thus the oracle performs
the termination and load-balancing computation on behalf of the processors.
for each processor
global T [1::N ];
while \not done" do
perform task T [Oracle-task(pid)]
od
end.

Figure

1: Oracle-based algorithm.
Lemma 3.1 [19, 16] The Do-All O (N; problem with f < P  N can be solved using work
log log P
Note that Lemma 3.1 does not teach how, if at all, work depends on f , the number of crashes.
Lemma 3.2 For any c > 0, Do-All O (N; f) can be solved for any stop-failure pattern with f
c P
log P using work
Proof : The proof is based on the proof of Theorem 3.6 of [16]. Let f denote the number of
processor stop-failures within a single iteration of the computation. f can be dierent for each
iteration, though the sum of these for all iterations cannot exceed f .
We set
2f , and we dene W (N; f) to be the work required to solve DoAll
O (N; Our goal is to show that for all U , P and f , the work W (U; f) is no more than
3P +U +P log P
U (= O(P +U +P log P
f
U )), where U  N denotes the number of undone tasks.
The proof proceeds by induction on U .
Base Case: Observe that when U  3, W (U;
desired.
Induction Case: Assume that we have proved the theorem for all U
U  N) and all P and
f . Consider
U . We investigate two cases:
Case 1:
U . In this case each processor is assigned to a unique task, hence
U P +f;P f; f f):
As
U
U and, by the induction hypothesis,
U
U P +f )]:
as desired.
Case 2:
U . In this case, by assumption we get
where
f) is the ratio of the number of the remaining tasks to ^
U (0
< 1).
the fraction of processors which fail during this iteration; then
< 2.
To see this, observe that
Uc
U
U
. Let
U , c > 1. Then
U
U
bcc
.
Now observe that 1  c
bcc
2:
Then
As
U , we may apply the induction hypothesis:
To complete the proof, it su-ces to show that for all  2 [0; f=P ],
U (1 )P log b(P;f) (
Upper bounding 3(1
dividing through by P , it is su-cient
to show that
or, equivalently,
log b(P;f)
3:
We now focus on the left hand side of the above equation:
log b(P;f)
log b(P;f)
log b(P;f)
U
log P , we have that 8P  2
2f > 2. [In particular, if
log b(P;f)
. (Note that if ^
f , then all tasks are completed in this iteration.)
Recall that
P . Therefore,
as desired.
From the induction proof and the denition of O(), we have
now give our main upper-bound result.
Theorem 3.3 Do-All O (N; f) can be solved for any failure pattern using work
Proof : This follows directly from Lemmas 3.1 and 3.2. 2
3.2 Do-All Lower Bounds
We now show matching lower bounds for Do-All O (N; Note that the results in this section
hold also for the Do-All(N; problem (without the oracle).
Lemma 3.4 [18, 16] For any algorithm Alg that solves Do-All O (N; there exists a pattern of
f stop-failures (f < P ) that results in work W
log log P
We now dene a specic adversarial strategy used to derive our lower bounds. Let Alg be any
algorithm that solves the Do-All problem. Let P i be the number of processors remaining at the
end of the i th step of Alg and let U i denote the number of tasks that remain to be done at the end
of step i. Initially,
log P , 0 <  < 1.
Adversary Adv: At step i (i  1) of Alg, the adversary stops processors as follows:
Among U i 1 tasks remaining after the step i 1, the adversary chooses U
tasks with the least number of processors assigned to them and crashes these processors.
The adversary continues for as long as U i > 1. As soon as U the adversary allows
all remaining processors to perform the single remaining task, and Alg terminates.
The following two Lemmas are used in the proof of Lemma 3.7.
Lemma 3.5 [18] If a 1 ; a is a sorted list of non-negative integers, then for all
Lemma 3.6 [18] Given G > 1; N > G, and integer  such that  < log N
log G 1, then the following
inequality holds:
| {z }
times
Lemma 3.7 Given any c > 0 and any algorithm Alg that solves Do-All O (N; the
adversary Adv causes f stop-failures, f  c P
log P , and
f
N).
By the denition of Adv, it follows that U
| {z }
times
. Using Lemma 3.6 with
, we get that  < log N
1. Recall that
log( P
f )+log log f
1. Then,
| {z }
times
0:
This tells us that adversary Adv will cause algorithm Alg to cycle through at least log N
log( P
f )+log log fiterations. Let  denote the number of iterations needed by Alg to terminate. Note that the algorithm
will cycle through at least one iteration, hence
log N
log( P
f )+log log f
Now, we need to compute a lower bound for P
am be the quantities of processors assigned to each task, sorted in
ascending order. Let am also include the quantity of any un-assigned processors, i.e., a 1 is the least
number of processors assigned to a task, a 2 is the next least quantity of processors, etc. Let
Thus the adversary stops exactly
processors.
At the beginning of iteration i, the number of processors
therefore, the number
of surviving processors
i=j+1 a i . Using Lemma 3.5, we get: P i  (1 U i
substituting for U and using the properties of
Observe that the work must be at least P    , where P  is the surviving processors after Alg ter-
minates. Consider two cases:
Case 1:
log P
log P
Let F  denote the total number of fail-stops after Alg terminates.
log P
log P  f , since log log P  log P
f  log P .
Therefore, adversary Adv did not cause more processor fail-stops than allowed.
The work caused by Adv in this case is:
f
log P
Case 2:
log( P
f )+log log f
log P
log N
log( P
f )+log log f P
log P
log P
log( P

log P

log P
log( P
f
Hence, Adv did not cause more fail-stops than allowed.
The work caused by Adv in this case is:

log N
log( P

log N
log N
f
log N
Note that W 2 > 0, since P log N
> P .
Now recall that f  c P
log P . Hence, 8P  2 2c we have that P
f > 2. [In particular, if
it su-ces P  4:]
From the above two cases and the denition of
we get that,
WN;P;f

log N
log( P
f
:Lemma 3.8 Given any c > 0 and any algorithm Alg that solves Do-All O (N;
there exists an adversary that causes f stop-failures, f  c P
log P , and
f
This follows from Lemma 3.7 and by slightly modifying adversary Adv. 2
We now give our main lower-bound result.
Theorem 3.9 Given any algorithm Alg that solves Do-All O (N; there exists an
adversary that causes
Proof : For the range of failures 0 < f  c P
log establishes the bound. From Lemma 3.8
we also obtain the fact that when
log P then work must
be
log log P
. For larger f
the adversary establishes this worst case work using the initial c P
log P failures. 2
3.3 Iterative Do-All
Do-All algorithms have been used in developing simulations of failure-free algorithms on failure-prone
processors. This is done by iteratively using a Do-All algorithm to simulate the steps of
the failure-free processors. We study the iterative Do-All problems to understand the complexity
implications of iterative use of Do-All algorithms.
It is obvious that r-Do-All(N; f) can be solved by running a Do-All(N;
times. If the work of a Do-All solution is W , then the work of the r-iterative Do-All is at most
r  W . However we show that it is possible to obtain a ner result. We refer to each Do-All iteration
as the round of r-Do-All O (N;
Theorem 3.10 r-Do-All O (N; can be solved with
denote the i th round of r-Do-All O (N; be the number of active processors
at the beginning of r i and f i be the number of crashes during r i . Note that P
the rst round of r-Do-All O (N; f) and that P i  We consider two cases:
Case 1: f > P r
log Consider a round r i . From Theorem 3.3 we get that the work for this round is
log
log
log log P i
However in this case, we can have f
log P ) for all r i without \running out" of processors.
Thus the work for this case is O(r
log log P )).
Case 2: f  P r
log First observe that any reasonable adversary would not kill more that P i
log
processors in round r i , since it would not cause more work than O(N
log
log log P i
(which is
achieved when f
log
Therefore, we consider f
log
for all rounds r i . Hence, the work in
every round r i (per Theorem 3.3) is O(N
log
log
log P
Let W (N; f) be this one-round upper bound. As
an upper bound on r-Do-
All O (N; f) can be given by maximizing
all such failure patterns. As
may assume that P for the purposes of the upper bound.
We show that this maximum is attained at f . For simplicity, treat f i as a
continuous parameter and consider the factor in the single round work expression (given above)
that depends on f
. (Here c is the constant hidden by the O() notation.) The rst
derivative over f i is d
c=log P
its second derivative is d 2
c=log P
Observe that the second derivative is negative in the
domain considered (and as long as P > 16). Hence the rst derivative is decreasing (with f i ). In
this case, given any two f the failure pattern obtained by replacing f i with
results in increased work. This implies that the sum
maximized when all f i s are equal, specically when f
As the above upper bound on the sum
in this range, it holds
in particular for the choices made by the adversary which must, of course, cause an integer number
of faults in each round. Therefore,
log Pr
f
)).
The result then follows from the denition of R r;P;f by combining the two cases. 2
Theorem 3.11 Given any algorithm that solves r-Do-All O (N; there exists a stop-
failure adversary that causes
r  (N +R r;P;f )):
Consider two cases:
Case 1: f > P r
log In this case the adversary may fail-stop P
log P processors in every round of r-
Do-All O (N; Note that for this
adversary
processors remain alive during the rst dr=2e
rounds. Per Theorem 3.9 this results in dr=2e
log log P
log log P ) work.
Case 2: f  P r
log In this case the adversary ideally would kill f
r processors in every round. It can
do that in the case where f divides r. If this is not the case, then the adversary kills d f
r e processors
in r A rounds and b f
r c in r B rounds in such a way that Again considering the rst
half of the rounds and appealing to Theorem 3.9 results in a
r(N +P log rP
f
lower bound for
work. Note that we consider only the case where r  f ; otherwise the work is
trivially
4 New Bounds for the Message-Passing Model
In this section we demonstrate the utility of the complexity results under the perfect load-balancing
assumption by giving a tight and complete analysis of the algorithm AN [5] and establish new
complexity results for the iterative Do-All in the message-passing model.
4.1 Analysis of Algorithm AN
Algorithm AN presented by Chlebus et al. [5] uses a multiple-coordinator approach to solve Do-
All(N; f) on crash-prone synchronous message-passing processors. The model assumes that messages
incur a known bounded delay and that reliable multicast [17] is available, however messages
to/from faulty processors may be lost.
The e-ciency of algorithm AN is characterized in terms of its work and message complexity.
We dene message complexity similarly to Denition 2.1 of work: For a computation subject to
a failure pattern F , F 2 F , denote by M i the number of point-to-point messages sent during
step i of the computation. For a given problem of size N , if the computation solves the problem
by step  in the presence of the failure pattern F , where jF j  F , then the message complexity M
is
Description of algorithm AN. Due to the space limitation, we give a very brief description of
the algorithm; additional details are given in the Appendix (but to avoid a complete restatement,
we refer the reader to [5]). Algorithm AN proceeds in a loop which is iterated until all the tasks
are executed. A single iteration of the loop is called a phase. A phase consists of three consecutive
stages. Each stage consists of three steps. In each stage processors use the rst step to receive
messages sent in the previous stage, the second step to perform local computation, and the third
step to send messages. A processor can be a coordinator or a worker . A phase may have multiple
coordinators. The number of processors that assume the coordinator role is determined by the
martingale principle: if none of the expected coordinators survive through the entire phase, then
the number of coordinators for the next phase is doubled. If at least one coordinator survives in a
given phase, then in the next phase there is only one coordinator. A phase that is completed with
at least one coordinator alive is called attended , otherwise it is called unattended .
Processors become coordinators and balance their loads according to each processor's local view .
A processor's local view contains the set of all processors ids that it assumes to be alive. The local
view is partitioned into layers. The rst layer contains one processor, the second two processors,
the third four processors and so on.
Given a phase, in the rst stage, the processors perform a task according to the load balancing
rule derived from their local views and report the completion of the task to the coordinators of that
phase (determined by their local views). In the second stage, the coordinators gather the reports,
they update the knowledge of the done tasks and they multicast this information to the processors
that according to their local views are alive. In the last stage, the processors receive the information
sent by the coordinators and update their knowledge of done tasks and their local views. Given
the full details of the algorithm, it is not di-cult to see that the combination of coordinators and
local views allows the processors to obtain the information that would be available from the oracle
in the algorithm in Figure 1.
It is shown in [5] that the work of algorithm AN is log N= log log N) log f) and
its message complexity is
New analysis of work complexity. To assess the work W , we consider separately all the
attended phases and all the unattended phases of the execution. Let W a be the part of W spent
during all the attended phases and W u be the part of W spent during all the unattended phases.
Hence we have . Note that P  N .
Lemma 4.1 [5] In any execution of algorithm AN with f < P we have W a
log log P )
and W
We now give the new analysis of algorithm AN.
Lemma 4.2 In any execution of algorithm AN we have W a = O(N +P log P
f
log P .
for any c > 0.
Given a phase i of an execution of algorithm AN, we dene p i to be the number of live
processors and u i to be the number of undone tasks at the beginning of the phase
all the attended phases of this execution (  is the last phase of the
execution).
Observe that for all  holds that
u a i
> u a i+1
, and
This follows from the construction of algorithm AN. Since phase  i is attended, there is at least one
coordinator, call it c, alive in phase  i . c executes one task. Hence, at least one task is executed and
consequently at least one task is taken out from u a i
. The number of processors can only decrease,
since we do not allow restarts.
Therefore, focusing only on attended phases, we can proof the lemma by induction on the size
of undone tasks U . Note that now the proof proceeds as the proof of Lemma 3.2 for P  N . 2
Theorem 4.3 In any execution of algorithm AN we have
This follows from Lemmas 4.1 and 4.2 and the fact that
Analysis of message complexity. To assess the message complexity M we consider separately
all the attended phases and all the unattended phases of the execution. Let M a be the number of
messages sent during all the attended phases and M u the number of messages sent during all the
unattended phases. Hence we have
Lemma 4.4 [5] In any execution of algorithm AN we have M a = O(W a ) and M
Theorem 4.5 In any execution of algorithm AN we have
Proof : The proof follows from Lemmas 4.1, 4.2 and 4.4 and the fact that
4.2 Analysis of Message-Passing Iterative Do-All
We now consider the r-Do-All(N; f) problem (P  N) in the message-passing model.
Theorem 4.6 The r-Do-All(N; f) problem can be solved on synchronous message-passing crash-
prone processors with work
r  (N
O(r  (N +R r;P;f
(Sketch.) The iterative Do-All can be solved by running algorithm AN on r instances of
size N in sequence. We call this algorithm AN*. To analyze the e-ciency of AN* we use the same
approach as in the proof of Theorem 3.10. In the current context we base our work complexity
arguments on the result of Theorem 4.3, and we base our message complexity arguments on the
result of Theorem 4.5. 2
5 New Bounds for the Shared-Memory Model
Here we give a new rened analysis of the most work-e-cient known Do-All algorithm for the
shared-memory model, algorithm W [18]. We also establish the complexity results for the iterative
Do-All and for simulations of synchronous parallel algorithms on crash-prone processors.
5.1 Analysis of Algorithm W
Algorithm W solves Do-All(N; f) in the shared-memory model (where Do-All is better known as
Write-All). Its work for any pattern of crashes is O(N
Note that this bound is conservative, since it does not include f , the number of crashes.
Description of the algorithm. We now give a brief description of the algorithm; additional
details can be found in Appendix (but to avoid a complete restatement we refer the reader to [19]).
Algorithm W is structured as a parallel loop through four phases: (W1) a failure detecting phase,
(W2) a load rescheduling phase, (W3) a work phase, and (W4) a phase that estimates the progress
of the computation, the remaining work and that controls the parallel loop. These phases use full
binary trees with O(N) leaves. The processors traverse the binary trees top-down or bottom-up
according to the phase. Each such traversal takes O(log N) time (the height of a tree). For a single
processor, each iteration of the loop is called a block-step; since there are four phases with at most
one tree traversal per phase, each block step takes O(log N) time.
In algorithm W the trees stored in shared memory serve as the gathering places for global
information about the number of active processors, remaining tasks and load balancing. It is not
di-cult to see that these binary trees indeed provide the information to the processors that would
be available from an oracle in the oracle model. The binary tree used in phase W2 to implement
load balancing and phase W3 to assess the remaining work is called the progress tree.
Here we use the parameterized version of the algorithm with P  N and where the progress
tree has leaves. The tasks are associated with the leaves of this tree, with
N=U tasks per leaf. Note that each block-step still takes time O(log N ).
New complexity analysis. We now give the work analysis. We charge each processor for each
block step it starts, regardless of whether or not the processor completes it or crashes.
Lemma 5.1 [19] For any failure pattern with f < P , the number of block-steps required by the
-processor algorithm W with U leaves in the progress tree is
log log P
Lemma 5.2 For any failure pattern with f  c P
log P (for any c > 0), the number of block-steps
required by the P -processor algorithm W with U leaves in the progress tree is
f
Processor block-steps can be shown to be equivalent to processor steps under the
perfect load-balancing assumption. Hence, the proof is the same as the proof of Lemma 3.2. 2
Theorem 5.3 Algorithm W solves Do-All(N;
We consider the following two cases:
Case 1: P < N
log Here the number of leaves in the progress tree is
log N and in the work phase
W3 each processor performs tasks. The cost of a single block-step is C
since each of the four phases takes at most log N time. We consider two subcases:
(a) f  P
log P . Lemma 5.2 gives the number of blocks-steps B 1a for this case as O(U
log P
f
O( N
log
log P
f
). Therefore the work W 1a for this case is B 1a  C
log P
f
log P
. Lemma 5.1 gives the number of block-steps B 1b for this case as O(U +P log P
log log P
O( N
log N +P log P
log log P ). Therefore the work W 1b for this case is B 1b C
log log P ).
These two subcases together with the denition of Q P;f yield W
Case 2: N
log N  P  N: Here the number of leaves in the progress tree is and in the work
phase W3 each processor performs d N
tasks. Thus the cost of a single block-step is
We consider two subcases:
(a) f  P
log P . Lemma 5.2 gives the number of block-steps B 2a for this case as O(U
log P
f
O(P+P log P
log P
f
log P
f
Therefore the work W 2a for this case is B 2a C
log P
f
log P
. Lemma 5.1 gives the number of block-steps B 2b for this case as O(P +P log P
log log P
O(P log P
log log P Therefore the work W 2b is B 2b  C
log log P ).
These last two subcases and the denition of Q P;f yield W Combining Case 1
and Case 2 results we get that
5.2 Iterative Do-All and Parallel Algorithm Simulations
We now consider the complexity of shared-memory r-Do-All(N; f) and of pram simulations.
Theorem 5.4 The r-Do-All(N; f) problem can be solved on P crash-prone processors (P  N ),
using shared memory, with work
(Sketch.) The iterative Do-All can be solved by running algorithm W on r instances of
size N in sequence. We call this algorithm W*. To analyze the e-ciency of W* we use the same
approach as in the proof of Theorem 3.10. In the current context we base our work complexity
arguments on the result of Theorem 5.3. 2
Now we state another main result in this paper.
Theorem 5.5 Any synchronous N-processor, r-time shared-memory parallel algorithm (pram)
can be simulated on P crash-prone synchronous processors with work O(r  (N +R r;P;f log N)).
Proof : The complexity of simulating a single parallel step of N ideal processors on P crash-prone
processors does not exceed the complexity of solving a single Do-All(N; instance [22, 30]. The
result then follows from Theorem 5.4. 2
6 Conclusions
In this paper we gave the rst complete analysis of the Do-All problem under the perfect load-balancing
assumption. We introduced and analyzed the iterative Do-All problem that models
repeated use of Do-All algorithms, such as found in algorithm simulations and transformations. A
unique contribution of our analyses is that they precisely describe the eect of crash failures on
the work of the computation. The analyses obtained with the perfect load-balancing assumption
are immediately useful, as they can be used to analyze algorithms and simulations that attempt to
balance the loads among the processors. Finally, we provided the rst failure-sensitive analysis of
work for the iterative Do-All problem in the message-passing and shared-memory models.



--R
































--TR
Efficient parallel algorithms can be made robust
Efficient robust parallel computations
Combining tentative and definite executions for very fast dependable parallel computing
Achieving optimal CRCW PRAM fault-tolerance
Efficient program transformations for resilient parallel computation via randomization (preliminary version)
Performing work efficiently in the presence of faults
Work-optimal asynchronous algorithms for shared memory parallel computers
On the complexity of certified write-all algorithms
Time-optimal message-efficient work performance in the presence of faults
Parallel algorithms with processor failures and delays
Algorithms for the Certified Write-All Problem
Fault-tolerant broadcasts and related problems
Fail-stop processors
SETI@HOMEMYAMPERSANDmdash;massively distributed computing for SETI
Fault-Tolerant Parallel Computation
Distributed Cooperation During the Absence of Communication
The Complexity of Synchronous Iterative Do-All with Crashes
Optimal F-Reliable Protocols for the Do-All Problem on Single-Hop Wireless Networks
Resolving message complexity of Byzantine Agreement and beyond
Parallelism in random access machines
Parallel processing on networks of workstations
Cooperative computing with fragmentable and mergeable groups

--CTR
Chryssis Georgiou , Dariusz R. Kowalski , Alexander A. Shvartsman, Efficient gossip and robust distributed computation, Theoretical Computer Science, v.347 n.1-2, p.130-166, November 2005
Antonio Fernndez , Chryssis Georgiou , Alexander Russell , Alex A. Shvartsman, The Do-All problem with Byzantine processor failures, Theoretical Computer Science, v.333 n.3, p.433-454, 3 March 2005
fault;work complexity;lower bounds;tolerence;distributed algorithms