Distributed Cooperation in the Absence of Communication
Greg Malewicz and Alexander Russell and Alex Shvartsman
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
This paper presents a study of a distributed cooperation problem under
the most extreme assumption that no two processors may be able to communicate
during the computation. The distributed cooperation problem is defined
for n processors in terms of t tasks that need to be performed efficiently
and that are known to all processors. The fact that the tasks are initially
known makes it possible for the problem to be solved in the absence of
communication, while the efficiency requirement and the possibility of
eventual availability of communication facilities make it necessary to
structure the work of the processors so that when some processors are able
to communicate, the amount of wasted (redundant) work they have collectively
performed prior to that point is controlled. Dolev et al. [DSS99] developed
a solution for this problem where each processor can perform up to >Q(n^(1/3))
tasks such that at most one redundant task is performed for any pair of
processors. In this work we show that for schedules longer than sqrt(n)
the number of redundant tasks for two (or more) processors must be at least
two. We also show that this bound is tight by exhibiting a construction
of schedules of length sqrt(n-3/4)+1/2 such that exactly one redundant
task is performed for any pair of processors. This design-theoretic construction
is efficient and practical: we show that it can be done in time linear
in the length of the schedule. We use this construction to produce, in
linear time, deterministic schedules of length 4n/9 such that pairwise
wasted work increases gracefully as processors progress through their schedules.
Finally we present a randomized solution, which demonstrates that if each
processor schedules the t tasks at random, then with high probability pairwise
intersections are well behaved at all times: specifically, two processors
having completed t_1 and t_2 tasks, respectively, are guaranteed to have
no more than (t_1 t_2)/t + >D redundant tasks, where >D = O(log n + sqrt((t_1
t_2)/t) sqrt(logg n)). This result contrasts favorably with the lower bound
we show, which asserts that pairwise schedule redundancy must grow quadratically
in the length of schedules. The redundancy incurred by collections of k
processors is also studied in our randomized framework.