The do-all problem in broadcast networks.
The problem of performing t tasks in a distributed system on p failure-prone processors is one of the fundamental problems in distributed computing. If the tasks are similar and independent and the processors communicate by sending messages then the problem is called Do-All. In our work the communication is over a multiple-access channel, and the attached stations may fail by crashing. The measure of performance is work, defined as the number of the available processor steps. Algorithms are required to be reliable in that they perform all the tasks as long as at least one station remains operational. We show that each reliable algorithm always needs to perform at least the minimum amount &OHgr;(t + pt) of work. We develop an optimal deterministic algorithm for the channel with collision detection performing only the minimum work &THgr;(t Another algorithm is given for the channel without collision detection, it performs work O(t is the number of failures. It is proved to be optimal if the number of faults is the only restriction on the adversary. Finally we consider the question if randomization helps for the channel without collision detection against weaker adversaries. We develop a randomized algorithm which needs to perform only the expected minimum work if the adversary may fail a constant fraction of stations, but it has to select the failure-prone stations prior to the start of an algorithm.
INTRODUCTION
We consider a distributed system in which p processors need
to perform t tasks. If the processors communicate by exchanging
messages, are prone to failures, and the tasks are
similar and independent then this problem is called Do-All .
In this paper we consider a setting in which the processors
are stations communicating over a multiple access channel.
The system is synchronized by a global clock. The channel
operates according to the following rules: if exactly one station
performs a broadcast in a step then the message reaches
all the stations, and if more of them broadcast simultaneously
in a step then mutual collisions happen and no station
successfully receives any of these messages. If the stations
attached to the channel do not receive a meaningful message
at a step then there are two possible reasons: either none or
more than one messages were sent. The ability to distinguish
between these two cases is called collision detection, when
it is available then the channel is with a ternary feedback,
because of the three possible events on the channel recorded
by the attached stations: (1) a meaningful message received,
(2) no messages sent, and (3) a collision signal received.
The stations are prone to fail-stop failures. Allowable patterns
of failures are determined by adversarial models. An
adversary is size-bounded if it may fail at most f stations,
for a parameter 0  f < p. We may refer to a size-bounded
adversary as f-bounded to make the value of parameter f ex-
plicit. If f is a constant fraction of p then the adversary is
linearly bounded. A size-bounded adversary is weakly adaptive
if it needs to select a subset of stations which might
be failed prior to the start of an algorithm, otherwise it is
strongly adaptive.
Our results. We consider Do-All in the context of a broadcast
network. More precisely, the communication is over
a multiple-access channel, either with or without collision
detection. We consider algorithms that are reliable in the
sense of being correct in the worst-case scenario when only
one station remains available. We show that the minimum
amount
of work has always to be performed by a
reliable algorithm. This is an absolute lower bound on work
performance of any algorithm, which does not depend on the
collision detection, randomization or the power of an adver-
sary. We show that in a channel with collision detection this
bound can be attained by a deterministic algorithm against
any size-bounded adversary. The situation is more complex
in a weaker channel without collision detection. We develop
a deterministic algorithm for this channel which performs
against f-bounded adver-
sary, even if the number of failures is the only restriction on
the power of the adversary. This is shown to be optimal by
a matching lower bound. Now it could happen that if we
wanted to optimize our solutions against weaker adversaries
then part O(p  minff; tg) in the performance bound could
be decreased. This indeed is the case: we show that a randomized
algorithm can have the expected minimum work
against certain weakly-adaptive size-bounded
adversaries. The conclusion is that randomization helps if
collision detection is not available and the adversary is suciently
restricted. The maximum number of faults when this
phenomenon happens is a constant fraction of the number of
all the stations. Next we show a lower bound which implies
that if only f-bounded
adversary with
can force any algorithm
for the channel without collision detection to perform
asymptotically more than the minimum work
t).
Previous work. The problem Do-All was introduced by
Dwork, Halpern, and Waarts [12], and investigated in a
number of papers [7, 9, 10, 11, 14]. All the previous papers
considered networks in which each node can send a message
to any subset of nodes in one step. The algorithmic
paradigms used included balancing work and checkpointing
the progress made. This includes using coordinators, which
are designated nodes to collect and disseminate information.
Dominant models of failures considered have been those of
fail-stop failures. The primary measures of e-ciency of algorithms
used in [12] were the task-oriented work, in which
each performance of a task contributes a unit, and communication
measured as the number of point-to-point messages.
This paper also proposed the eort as a measure of per-
formance, which is work and communication combined; one
algorithm presented in [12] has eort O(t
p).
The early work assuming fail-stop failures model has concentrated
on the adversary who could fail all the stations
but one. More recent work concerned optimizing solutions
against weaker adversaries, while preserving correctness in
the worst-case scenario of arbitrary failure patterns, which
guarantee only at least one available processing unit.
De Prisco, Mayer, and Yung [11] were the rst to use the
available processor steps as the measure of work. They
present an algorithm which has work O(t+(f+1)p) and message
complexity O((f +1)p). Galil, Mayer and Yung [14] improved
the message complexity to O(fp " +minff+1; log pgp),
for any positive ", while maintaining the same work. This
was achieved as a by-product of their work on Byzantine
agreement with stop-failures, for which they found a message-
optimal solution. Chlebus, De Prisco, and Shvartsman [7]
studied failure models allowing restarts. Restarted processors
could contribute to the task-oriented work, but the cost
of integrating them into the system, in terms of the available
processor-steps and communication, might well surpass
the benets. The solution presented in [7] achieves
the work performance O((t
and its message complexity is O(t against
suitably dened adversaries who may introduce f failures
and restarts. This algorithm is an extension of one that
is tolerant of stop-failures and which has work complexity
log p= log log p) log f) and communication complexity
[10] studied the Do-All problem when failure patterns are
controlled by weakly-adaptive linearly-bounded adversaries.
They developed a randomized algorithm with the expected
eort O(n log  n), in the case t, which is asymptotically
smaller than a known lower
bound
log n= log log n)
on work of any deterministic algorithm. Recently, strongly-
adaptive linearly-bounded adversaries have been studied by
Chlebus, Gasieniec, Kowalski and Shvartsman [9] who developed
a deterministic algorithm with the eort O(n log 2 n).
This is the rst algorithm known with a performance bound
of the form O(n polylog n) when as many as a linear fraction
of processing units can be failed by an adversary, all the
previously known algorithms had the
performance
such a situation. Note however, that neither work nor communication
performances should be used as the only criteria
to compare algorithmic solutions of Do-All ; such algorithms
are usually designed for concrete environments and
optimized for specic adversaries.
Related work. The multiple-access channel, as considered
in this paper, is a special broadcast network ([4, 33]).
It may be also interpreted as a single-hop radio network,
especially in the context of the relevance of collision de-
tection, see e.g. [6]. Most of the previous research on the
multiple-access channel has concerned methods of handling
packets which the stations keep receiving and which need
to be broadcast on the channel as soon as possible. The
packets may be generated dynamically in a possibly irregular
way which results in a bursty tra-c. Techniques like
time-division multiplexing are not e-cient then, and a better
throughput can be achieved if the control is distributed
among the stations. This is done by con
ict-resolution pro-
tocols, which arbitrate among the stations competing for
access to the channel; among the most popular protocols is
Aloha and the exponential backo. If packets are generated
dynamically then the basic problem is to have stable proto-
cols, which do not make the channel clogged eventually. Recent
work in that direction includes the papers of Goldberg,
MacKenzie, Paterson and Srinivasan [16], Hastad, Leighton
and Rogo [20], and Raghavan and Upfal [31]; see also the
survey of Gallager [15] for an account of the early research
and that of Chlebus [6] for recent developments.
Static problems concern a scenario when input data are allocated
at the stations prior to the start of an algorithm. The
problem of selection concerns the situation when some of
the stations hold messages, the goal is to broadcast just any
single message successfully. Willard [34] developed protocols
solving the problem in the expected time O(log log n) in
the channel with collision detection. Kushilevitz and Mansour
[27] proved a lower bound
nd n) for the selection
problem if collision detection is not available, which yields
an exponential gap between two models for this problem. A
related problem of nding maximum among the keys stored
in a subset of stations was considered by Martel [28].
There is a related all-broadcast problem, in which a subset
of k among n stations have messages, all of them need to be
sent to the channel successively as soon as possible. Komlos
and Greenberg [26] showed how to solve it deterministically
in time O(k log(n=k)), where both numbers n and k are
known. A lower
bound
k(log n)=(log k)) was proved by
Greenberg and Winograd [18].
Gasieniec, Pelc and Peleg [17] compared various modes of
synchrony in multiple-access channel in the context of the
wakeup problem, in which the system is started and the time
when each station joins is controlled by an adversary, while
the goal is to perform a successful broadcast as soon as pos-
sible. If the stations have access to a global clock then a
wakeup can be realized in the expected time O(log n) by
a randomized algorithm. If the local clocks are not syn-
chronized, there is a randomized solution working in the
expected time O(n). It was also shown in [17] that deterministic
algorithms require
time
n), and that there are
deterministic schedules working in time O(n log 2 n).
Problem Do-All specialized to shared-memory models is called
the operation of reading/writing from a memory
cell/register is considered to be an individual task. More
precisely, in this problem p failure prone processors need to
update t shared memory locations. A solution to this problem
can be applied to simulate a step of computation of a
shared-memory computer, and thus make its computations
resilient to processor faults. The problem Write-All was introduced
by Kanellakis and Shvartsman [21]. Algorithms
for the Write-All problem have been developed in a series
of papers, including those by Anderson and Woll [3], Buss,
Kanellakis, Ragde and Shvartsman [5], Chlebus, Dobrev,
Kowalski, Malewicz, Shvartsman, and Vrto [8], Groote, Hes-
selink, Mauw, and Vermeulen [19], Kedem, Palem, Rabin
and Raghunathan [23], Kedem, Palem, Raghunathan and
Spirakis [24], Kedem, Palem and Spirakis [25], Martel, Park
and Subramonian [29], and Martel and Subramonian [30].
A comprehensive account of algorithms for the Write-All
problem can be found in a book by Kanellakis and Shvartsman
[22].
There is another related problem called Collect, it was introduced
by Saks, Shavit and Woll [32]. It is about a number of
processes, each containing a value in a shared memory regis-
ter: the goal the processes need to achieve is to learn all the
values. A process increases its knowledge in a step by reading
a register: then it can add the read value to the contents
of its own register. The number of read/write operations is
a measure of performance. There is an adversary who controls
timing of the processes in an asynchronous computa-
tion. Ajtai, Aspnes, Dwork and Waarts [1] showed that the
problem for n processes can be solved deterministically with
work O(n 3=2 log n), by an adaptation of the algorithm of Anderson
and Woll [3]. Aspnes and Hurwood [2] developed a
randomized algorithm achieving work O(n log 3 n) with high
probability. A lower
bound
log n) for this problem was
given in [32].
2. MODEL
Processing units. There are p stations, each with a unique
identier ID in [1::p]. The station P with identier
i is denoted as P i . The system is synchronized by a global
clock.
Communication. Stations communicate by broadcasting
on a multiple access channel. This model is also called a
single-hop radio network [6], and we often say that a station
can hear the information it receives from the channel.
We assume that all the messages sent on the channel are
delivered to all the stations, but if many are sent simultaneously
then they interfere with each other and are received
as garbled. The size of a packet to carry a single message is
assumed to be O(log p) bits, but all our deterministic algorithms
broadcast messages of merely O(1) bits.
If a message sent on the channel is heard by a station then
the message is said to be successfully delivered to it. This
happens if exactly one station broadcasts a message: then it
is heard by all the stations by the end of the next step. If no
messages are sent then the stations can hear only the background
noise, which is distinct from any meaningful mes-
sage. If more than one messages are broadcast simultaneously
in a step then a collision happens, and no station can
hear any of these messages. We consider two models depending
on what feedback the stations receive if a collision
happens.
Channel without collision detection: each station can hear
the background noise.
Channel with collision detection: each station can hear the
interference noise, which is distinct from the background
noise.
Failures. Stations fail by crashing. A station which has
not failed yet at a step is said to be operational in this step.
Failure patterns are generated by adversaries. Adversarial
models allowing restarts are not considered [7]. An adversary
knows the algorithm against which it competes. An
adversary is said to be adaptive with condition C if it may
make its decisions on-line, the only constraint being that
the condition C has to be satised in each execution. We
consider the following specic adversaries:
Strongly-Adaptive f-Bounded: is adaptive with the condition
that at most f stations are failed, where 0  f < p.
Weakly-Adaptive f-Bounded: it is adaptive with the
following condition, where 0  f < p:
(1) It needs to select f failure-prone stations prior to the
start of an algorithm;
(2) It may fail only the selected failure-prone stations in the
course of an algorithm.
We write simply f-Bounded for Strongly-Adaptive f-
Bounded. The adversary Unbounded is the same as
(Strongly-Adaptive) (p 1)-Bounded. There is no difference
in power between strongly and weakly-adaptive size-
bounded adversaries when they compete against deterministic
algorithms. The adversary Linearly-Bounded denotes
f-Bounded, where
of the considered adversaries may fail all the stations in an
execution of an algorithm.
Complexity measures. The principal measure is work,
which is dened to be the number of available-processor
steps: each station contributes a unit for each step when it is
operational, even when idling. To have the measure dened
precisely, we need to know when an algorithm starts and
when it terminates. The stations are provided with input
and the time-step to begin, we start counting the available-
processor steps from this moment. Each station may come
to a halt state at any time, only when it does so then it
stops contributing to work. A station which halted in this
way is considered non-faulty, hence halts do not restrict the
power of adversaries.
Tasks. There are t tasks given as input. They are known
to all the stations. The following three properties of tasks
are essential:
similar: each takes one step to perform;
independent: can be performed in any order;
idempotent: can be performed many times and concurrently.
The problem Do-All is to perform a given set of tasks with
these properties, in a message passing network with processing
units prone to failures.
Correctness. We require algorithms to be correct against
any strategy of the adversary Unbounded. We call such
algorithms reliable. Formally, an algorithm solving the DoAll
problem is reliable if the following two conditions are
(1) All the tasks are eventually performed, if at least one
station remains non-faulty;
(2) All the stations eventually halt, unless failed.
In proofs of lower bounds, we mean an execution of an algorithm
to be a sequence of congurations of the system
in consecutive steps, including the failure pattern, the messages
broadcast on the channel, and the sequence of random
bits used by each station [13]. If an execution E 0 is obtained
by modifying the actions of an adversary on some other execution
E, then it is assumed that each station in E 0 receives
exactly the same sequence of random bits as in E.
If a reliable algorithm is run then no station halts when
there are still tasks that have not been completed yet: the
remaining stations may be killed and the halted station will
not perform any more tasks. This property can be strengthened
quantitatively as follows:
Lemma 1. A reliable algorithm, possibly randomized, has
to perform
work
in each execution, even if no
failures happen.
Proof. It is su-cient to consider the channel with collision
detection, in which algorithms have more information.
Part
t) of the bound follows from the fact that each task
has to be performed at least once.
A task  is conrmed at step i, in an execution of the algo-
rithm, if either a station broadcasts successfully and it has
performed  by step i, or more than one station broadcast
simultaneously and all of them, with a possible exception of
one station, have performed  by step i. At least half of
the stations broadcasting in step i and conrming  have
performed it by then, so at most 2i tasks can be conrmed
in step i. Let E1 be an execution of the algorithm when no
failures happen. Let station P come to a halt at some step
in E1 .
Claim: the tasks not conrmed by step j were performed
by P itself in E1 .
Suppose, on the contrary, that this is not the case, let  be
such a task. Consider an execution E2 obtained by running
the algorithm and killing any station that performed  in
E1 just before it was to perform , and all the remaining
stations, except for P, killed at step j. The broadcasts on
the channel are the same during the rst j steps in E1 and
E2 . Hence all the stations perform the same tasks in E1 and
E2 till step j. The denition of E2 is consistent with the
power of the adversary Unbounded. The algorithm is not
reliable because task  is not performed in E2 and station
P is operational. This justies the claim.
We estimate the contribution of station P to work: The total
number of tasks conrmed in E1 is at most 2(1+2+: :
tasks have been conrmed by step
j. The remaining t t 0 tasks have been performed by P.
The work of P is at
least
t).
The amount of work asymptotically equal to t+p
t is called
shows that the minimum work is an
absolute lower bound on the amount of work performed by
a reliable algorithm in any scenario. The minimum work is
a yardstick we will use in the following sections to measure
the performance of algorithms.
3. CHANNEL WITHOUT COLLISION DE-
TECTION
We develop a deterministic algorithm TwoLists. The algorithm
avoids con
icts between broadcasting stations: at
each time-step there is at most one station scheduled to
broadcast. A broadcast message may consist of just a single
bit, since its only purpose is to conrm that the station
is still alive. A station does not need to announce which
tasks it performed, since all the stations can compute this
themselves.
The stations have the same global knowledge implied by
what was broadcast on the channel. Each station maintains
two circular lists: TASKS and STATIONS. The items in TASKS
are the tasks still not announced on the channel as per-
formed, and the items in STATIONS are the stations which
either made a broadcast each time they were to do so or were
not scheduled to broadcast yet at all. Since these lists are
dened by what happened on the channel, they are exactly
the same in every station.
There is a pointer associated with each of the lists. Let
Station denote the station pointed on the list STATIONS
and Task be the task pointed on the list TASKS. The pointers
provide reference points to assign tasks to stations: Task is
assigned to Station, then the next task on TASKS is assigned
to the next station on STATIONS, and so on in the circular
order. Notice that a task can be assigned to a number of
stations if the list STATIONS winds around the list TASKS
during the assignment process.
Each station performs:
a) its assigned task
b) the rst task not performed by it yet located after Task
(2) Counter is decremented by one; if Counter  0 then the stations halt
(3) If jTASKSj < Shift then Shift := dShift=2e
Station performs a broadcast
(5) If a broadcast is heard then
a) the tasks performed by Station are removed from TASKS
b) if TASKS is empty then the stations halt
c) the pointer on STATIONS is advanced by one position
else Station is removed from STATIONS
(6) The pointer on TASKS is advanced by d
Shifte positions

Figure

1: Algorithm TwoLists: a phase.
After a scheduled broadcast one of the lists is updated as
follows. If a successful broadcast happened then the tasks
which have been performed by the broadcasting station are
removed from TASKS. If a broadcast did not happen then the
station which failed to broadcast is removed from the list
STATIONS. If an item pointed at by the pointer is removed
from a list then the pointer is assigned automatically to
the next item on the list. Other then that the pointers
are updated as follows: pointer Task is moved by d
Shifte
positions, and pointer Station is always advanced by one
position.
The variable Shift is initialized to dt=2e. The lists TASKS
and STATIONS are initialized to contain all the tasks and
stations, respectively, ordered by their identiers. The size
a phase is given in Figure 1.
Lemma 2. Algorithm TwoLists is reliable.
The next theorem shows how the performance of TwoLists
degrades gracefully with the number of faults.
Theorem 1. Algorithm TwoLists performs work O(t
against the adversary f-Bounded, for
Proof. For the purpose of the argument, the time of
computation is partitioned conceptually into rounds: during
a round the value of Shift is constant. If no broadcast is
heard at a step then both the work performed by all the
stations at this step and the work performed by the station
that was to broadcast (since its last successful broadcast) is
at most 2p. There are O(minff; tg) such rounds, because a
station performs a new task in each phase, unless failed.
Consider the work performed by broadcasting stations during
a round. The work performed while jSTATIONSj 2
Shift is estimated as follows. Each task performed and
reported was performed only once in that way, and this can
be charged to O(t).
Consider next the work performed while jSTATIONSj 2 > Shift.
A segment of consecutive items on STATIONS of size d
Shifte,
starting from Station, perform dierent tasks in a step.
Each of these stations is eventually heard, if not failed, so
this work can be charged to O(p
Shift). The values of
Shift are a geometrically decreasing sequence, hence summing
over rounds gives the estimate O(p
t).
Next we show a matching lower bound.
Theorem 2. The adversary f-Bounded, for 0  f < p,
can force any reliable randomized algorithm for the channel
without collision detection to perform
work
Proof. We consider two cases, depending on which term
dominates the bound. If it is
t) then the bound follows
from Lemma 1. Consider the case
when
is the bound. Let
Let E1 be an execution obtained by running the algorithm
and killing any station that wants to broadcast successfully
during the rst g=4 steps. Denote as A the set of stations
failed in E1 . The denition of E1 is consistent with the
power of the adversary f-Bounded, since jAj  g=4  f .
no station halts by step g=4 in the execution E1 .
Suppose, on the contrary, that some station P halts before
step g=4 in E1 . We show that algorithm is not reliable.
To this end we consider another execution E2 , which can
be realized by the adversary Unbounded. Let
be a task
Each station performs:
a) task assigned to its group
b) the rst task after Task not performed by it yet
(2) Counter is decremented by one; if Counter  0 then the stations halt
(3) If jTASKSj < Shift then Shift := dShift=2e
Each station in Group performs a broadcast
(5) If a broadcast was heard, including a collision, then
a) the tasks performed by Group are removed from TASKS
b) if TASKS is empty then the stations halt
c) the pointer on GROUPS is advanced by one position
else Group is removed from GROUPS
(6) The pointer on TASKS is advanced by d
Shifte positions

Figure

2: Algorithm GroupsTogether: a phase.
which is performed in E1 by at most pg=(4(t g=4))
stations except P during the rst g=4 steps. It exists
because g  t. Let B be this set of stations, we have jBj
pg=(3t)  p=3. We dene operationally a set C of stations as
follows. Initially C equals A[B; notice jA [Bj  7p=12. If
there is any station that wants to broadcast during the rst
g=4 steps in E1 as the only station not in the current C then
it is added to C. At most one station is added to C for each
among the rst g=4  p=4 steps of E1 , so jCj  10p=12 < p.
Let an execution E2 be obtained by failing all the stations
in C at the start and then running the algorithm. The
denition of E2 is consistent with the power of the adversary
Unbounded. There is no broadcast heard in E2 during the
rst g=4 steps. Therefore each station operational in E2
behaves in exactly the same way in both E1 and E2 during
the rst g=4 steps. Task
is not performed in execution E2
by step g=4, because the stations in B have been failed and
the remaining ones behave as in E1 .
Station P is not failed during E2 hence it does the same
both in E1 and in E2 . Consider an execution E3 : it is like
E2 till step g=4, then all the stations except P are failed. The
denition of E3 is consistent with the power of the adversary
Unbounded. Station P is operational but halted and task
is still outstanding in E3 at step g=4. We conclude that
the algorithm is not reliable. This contradiction completes
the proof of the claim.
Hence there are at least p
stations still operational
and non-halted in step g=4 in E1 , and they have
generated
work
pg) by then.
Corollary 1. Algorithm TwoLists is asymptotically op-
timal, among reliable randomized algorithms for the channel
without collision detection, against the f-Bounded adver-
This shows that randomization does not help against the
strongest possible size-bounded adversaries for the channel
without collision detection. In Section 5 we show that randomization
can make a dierence for this channel in weaker
adversarial models.
4. CHANNEL WITH COLLISION DETEC-
TION
We develop a deterministic algorithm GroupsTogether.
The algorithm is a suitable modication of TwoLists. The
main dierence is that while TwoLists avoids con
icts by
its design, the algorithm in this section uses con
icts aggressively
as a hedge against faults. Algorithm GroupsTo-
gether is in phases repeated in a loop, a phase is given if

Figure

2.
The algorithm maintains two lists. List TASKS is the same
as in Section 3. The stations are partitioned into groups,
which are maintained as a circular list GROUPS. There is a
pointer which points to Group. The stations in the same
group always perform the same tasks and broadcast simul-
taneously. The tasks are assigned to groups as follows: Task
is assigned to Group, then the next task is assigned to the
next group, and so on in the circular orders on both lists.
The way the lists are updated after a scheduled broadcast
depends on the fact if a broadcast happened, which is detected
by receiving either a message or a signal of collision.
When a broadcast happens then the tasks performed by the
group just heard on the channel are removed from TASKS.
If a broadcast did not happen then Group is removed from
GROUPS. If an item which is pointed at by the associated
pointer is removed from a list then the pointer is automatically
advanced to the following item. Other then that the
pointers are updated as follows: pointer Task is moved by
d
Shifte positions, and pointer Group is always advanced
by one position.
The stations are partitioned initially into minfd
groups, this partitioning is never changed in the course
(1) If STATIONS is empty then the control is returned to the algorithm
(2) Each station in STATIONS tosses a coin with the probability jSTATIONSj 1
of heads to come up
(3) A station that obtained heads broadcasts its ID on the channel
(4) If number i was heard then station P i is removed from STATIONS and
appended to SELECTED

Figure

3: Mixing: a phase.
of the algorithm. The lists TASKS and GROUPS are initialized
to contain all the tasks and groups, respectively, and are
ordered by the identiers of items. The variable Shift is
initialized to dt=2e. Variable Counter is initialized to t.
Lemma 3. Algorithm GroupsTogether is reliable.
Theorem 3. Algorithm GroupsTogether performs only
the minimum work
against the adversary f-
Bounded, for 0  f < p.
Proof. Rounds are dened as in the proof of Theorem 1.
If no broadcast is heard at a step then the work performed
by all the stations at this step and the stations that were to
broadcast (since their last successful broadcast) is at most
2p. There are at most O(
t) such rounds because of the
total number of groups.
Consider the work performed by broadcasting groups during
a round. The work performed while jGROUPSj 2  jTASKSj
is estimated as follows. Each task performed and then reported
was performed by only one group in that way. If
groups contain O(1) stations then this can be charged to
O(t), otherwise to O(p
t).
Consider next the work performed while jGROUPSj 2 > jTASKSj.
The number stored in the variable d
Shifte has the property
that these many groups in list GROUPS perform distinct
tasks in a step. Each of these groups was heard, if not
failed, so this work can be charged to O(p
Shift). The
values of Shift make a geometrically decreasing sequence,
hence summing over rounds gives the estimate O(p
t).
The fact that the algorithm GroupsTogether needs to
perform only the minimum amount of work has the following
two consequences:
Corollary 2. Algorithm GroupsTogether is asymptotically
optimal, among reliable randomized algorithms for
the channel with collision detection, against the strongest
size-bounded adversaries.
Corollary 3. Algorithm GroupsTogether cannot be
beaten in asymptotic work performance by any randomized
reliable algorithm in any weaker adversarial model in which
not all stations can be failed.
5. RANDOMIZED SOLUTIONS
We have shown that randomization does not help against
strongly-adaptive size-bounded adversaries. Corollary 3 implies
that this is also the case for the channel with collision
detection against weaker adversaries. In this section we
show that, as far as the channel without collision detection is
concerned, the power of a size-bounded adversary does matter
if we compare the optimal performance of deterministic
algorithms versus randomized ones.
We develop a randomized algorithm MixThenWork. It selects
a su-ciently long random set of stations, which then
run a suitably modied algorithm TwoLists. The algorithm
uses the same lists and pointers as TwoLists. Ad-
ditionally, there is a cyclic list SELECTED of stations, also
with a pointer. The process of random selection of stations
is performed by procedure Mixing. It iterates phases in a
loop, as described in Figure 3.
Next we describe procedure AltTwoLists. It operates by
having the stations on list SELECTED run TwoLists, with
SELECTED playing the role of STATIONS. The remaining stations
in STATIONS, if any, do not make any attempts to
broadcast then. Instead, they listen to the channel to learn
about tasks performed by other stations and keep performing
consecutive tasks still in TASKS. A task is removed from
TASKS by a station only if it was performed by a station that
managed to broadcast on the channel, otherwise it is just
marked as done. This allows to maintain the same items on
the instances of the list TASKS by all the stations. A station
halts when it has all the tasks on its copy of TASKS marked
as done. Procedure AltTwoLists returns control, and a
new iteration starts, as soon as all the stations in SELECTED
fail to broadcast in their assigned time slots. The whole
algorithm MixThenWork is described in Figure 4.
Lemma 4. Algorithm MixThenWork is reliable.
Theorem 4. The expected work performed by the algorithm
MixThenWork against the adversary
Weakly-Adaptive Linearly-Bounded equals the minimum
t).
Proof. If all the stations are in the list
SELECTED from the start and all stations execute TwoLists
algorithm performing work O(t).
Iterate in a loop:
(1) If jTASKSj < jSTATIONSj 2 then
jTASKSj phases of Mixing are performed,
else all the stations are moved to SELECTED
(2) Procedure AltTwoLists is called

Figure

4: Algorithm MixThenWork.
Consider the case p 2  t. A new station is added to the list
SELECTED in a phase of Mixing with some constant prob-
ability. The number of phases of the rst call of Mixing
is O(
t). It follows from the denition of the adversarial
model and by the Cherno bound that there
are
stations in SELECTED that are not failure-prone, after this
rst call, with the probability at least 1 e a
t , for some
a > 0. If this event holds then there is just one iteration
of the loop in the algorithm, and the bound O(p
t) on the
work follows. Only a constant fraction of (
stations executing
algorithm TwoLists may fail with the probability
t . Hence the work done by these ( p
stations
is O(t) by Theorem 1. In the meantime, as many as O(p)
other stations listening to the channel perform work, which
is O(p=
times larger than work performed by the selected
stations. Hence the total work is O(t
with the respective large probability.
Otherwise the work is O(pt). The total expected work is
thus of order
t(1 e a
which is within the claimed bound.
Is there an algorithm that needs to perform only the expected
minimum work against such weakly-adaptive adversaries
who could fail asymptotically more than a constant
fraction of the stations? Corollary 4 answers this question
in the negative for certain values of p, f and t. We show the
following precise lower bound:
Theorem 5. The Weakly-Adaptive f-Bounded adversary
can force any reliable randomized algorithm for the
channel without collision detection to perform the expected
work
Proof.
Part
t) follows from Lemma 1. We show
the remaining one. Let number g  f be a parameter, we
will set its value later in the proof. Consider the following
experiment: the algorithm is run for g steps, and each
station which wants to broadcast successfully is failed just
before it is to do so. Additionally, at step g, a su-cient
number of the remaining stations, say, those with the smallest
identiers, is failed to make the total number of failures
by step g equal to exactly g. We dene a probabilistic space
in which the elementary events are the sets of IDs of stations
corresponding to sets of size g which can be failed in
the experiment. Let F denote the family of all such elementary
events. The probability Pr(!) of ! 2 F is dened to
be equal to the probability of an occurrence of an execution
during the experiment, in which exactly the stations with
IDs in ! are failed by step g.
The following equality holds

where we sum over subsets A  [1::p] and elementary events
because each Pr(!) occurs p g
times on the left-hand
side. There are p
subsets A  [1::p] with
. Hence there is some C  [1::p], with
such that the probability that the IDs of stations failed in
the experiment are all outside C is at least


O(1), which is the case if g
Let the adversary declare exactly the stations not in C as
prone to failures. Suppose the algorithm is run for minfh; tg=4
steps and each station not in C which is to broadcast successfully
is failed just before it attempts to do so. Such an
execution is consistent with the power of the adversary. The
event that no message is heard during minfh; tg=4 steps has
the
probability
376 Simultaneously, the number of operational
stations is
p). None of these stations may halt by
step minfh; tg=4, by an argument similar to that used in the
proof of Theorem 2: the algorithm would prove not to be
reliable because this step occurs earlier than minff; tg=4.
The expected work in such an execution is thus of order
de p minfh=4;
which completes the
proof.
Corollary 4. If
then the adversary
Weakly-Adaptive f-Bounded can force any algorithm
for the channel without collision detection to perform
6. CONCLUSIONS
We study solutions to the Do-All problem in the context
of synchronous broadcast networks. The questions we ask
are as follows: What is the impact of the availability of
collision detection? Does randomization help? How does the
e-ciency of solutions depend on various adversarial models?
We show that all these parameters have an impact.
Most of the previous research on the multiple-access channel
has concerned the issues of stability of protocols handling
dynamically generated packets. There have been quite few
static algorithmic problems considered, in which the whole
input is provided to the attached stations in advance. The
broadcast channel is ubiquitous in local area networks, and
all its algorithmic aspects deserve a study, those concerning
static problems in particular. This paper attempts to
demonstrate that this is the case for the problem Do-All .
7.



--R

A theory of competitive analysis of distributed algorithms
Spreading rumors rapidly despite an adversary
Algorithms for the certi

Parallel algorithms with processor failures and delays
Randomized communication in radio networks
Performing tasks on synchronous restartable message-passing processors


Randomization helps to perform tasks on processors prone to failures

Performing work e-ciently in the presence of faults
Lower bounds in distributed computing
Resolving message complexity of byzantine agreement and beyond
A perspective on multiaccess channels
Contention resolution with constant expected delay

A lower bound on the time needed in the worst case to resolve con icts deterministically in multiple access channels
An algorithm for the asynchronous write-all problem based on process collision




Combining tentative and de





On the complexity of certi
Stochastic contention resolution with short delays
Optimal time randomized consensus - making resilient algorithms fast in practice


--TR
Correction to "An asymptotically nonadaptive algorithm for conflict resolution i
Data networks
Log-logarithmic selection resolution protocols in a multiple access channel
Efficient robust parallel computations
Combining tentative and definite executions for very fast dependable parallel computing
Optimal time randomized consensusMYAMPERSANDmdash;making resilient algorithms fast in practice
Efficient program transformations for resilient parallel computation via randomization (preliminary version)
Work-optimal asynchronous algorithms for shared memory parallel computers
On the complexity of certified write-all algorithms
Maximum finding on a multiple access broadcast network
Time-optimal message-efficient work performance in the presence of faults
A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
Parallel algorithms with processor failures and delays
Analysis of Backoff Protocols for Mulitiple AccessChannels
Computer networks (3rd ed.)
Algorithms for the Certified Write-All Problem
An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
Spreading rumors rapidly despite an adversary
Performing Work Efficiently in the Presence of Faults
Stochastic Contention Resolution With Short Delays
The wakeup problem in synchronous broadcast systems (extended abstract)
Contention resolution with constant expected delay
Towards practical deteministic write-all algorithms
Fault-Tolerant Parallel Computation
Randomization Helps to Perform Tasks on Processors Prone to Failures
Lower Bounds in Distributed Computing
Resolving message complexity of Byzantine Agreement and beyond

--CTR
Dariusz R. Kowalski , Alex A. Shvartsman, Performing work with asynchronous processors: message-delay-sensitive bounds, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.265-274, July 13-16, 2003, Boston, Massachusetts
Bogdan S. Chlebus , Dariusz R. Kowalski, Randomization helps to perform independent tasks reliably, Random Structures & Algorithms, v.24 n.1, p.11-41, January 2004
Dariusz R. Kowalski , Alex A. Shvartsman, Performing work with asynchronous processors: message-delay-sensitive bounds, Information and Computation, v.203 n.2, p.181-210, December 15, 2005
Bogdan S. Chlebus , Dariusz R. Kowalski , Mariusz A. Rokicki, Adversarial queuing on the multiple-access channel, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
fail-stop failures;independent tasks;multiple-access channel;lower bound;adversary;distributed algorithm