TY - GEN

T1 - Bounding work and communication in robust cooperative computation

AU - Chlebus, Bogdan S.

AU - Gąsieniec, Leszek

AU - Kowalski, Dariusz R.

AU - Shvartsman, Alex A.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - We consider the Do-All problem: p failure-prone processors perform t similar and independent tasks. We assume that processors are synchronous, communicate by message passing, and are subject to crashes determined by an adaptive adversary restricted only by the upper bound f on the number of crashes. The performance of algorithms in this setting is normally measured in terms of work (total available processor steps) and communication (total number of point-to-point messages) complexity. We consider work and communication as comparable resources and we develop algorithms that have efficient effort defined as work + communication. We present a p-processor, t-task algorithm that has effort O(t+p1.77), against the unbounded adversary (f < p). This is the first algorithm that achieves subquadratic in p effort efficiency for unbounded adversary, or even for linearly-bounded adversary that crashes up to a constant fraction of the processors.We present another algorithm that has work O(t + p log2 p) against f-bounded adversaries such that p−f = Ω(pb) for a constant b, 0 < b < 1. We show how to achieve effort O(t + p log2 p) against a linearly-bounded adversary; this result is close to lower bound Ω(t + p log p/ log log p).

AB - We consider the Do-All problem: p failure-prone processors perform t similar and independent tasks. We assume that processors are synchronous, communicate by message passing, and are subject to crashes determined by an adaptive adversary restricted only by the upper bound f on the number of crashes. The performance of algorithms in this setting is normally measured in terms of work (total available processor steps) and communication (total number of point-to-point messages) complexity. We consider work and communication as comparable resources and we develop algorithms that have efficient effort defined as work + communication. We present a p-processor, t-task algorithm that has effort O(t+p1.77), against the unbounded adversary (f < p). This is the first algorithm that achieves subquadratic in p effort efficiency for unbounded adversary, or even for linearly-bounded adversary that crashes up to a constant fraction of the processors.We present another algorithm that has work O(t + p log2 p) against f-bounded adversaries such that p−f = Ω(pb) for a constant b, 0 < b < 1. We show how to achieve effort O(t + p log2 p) against a linearly-bounded adversary; this result is close to lower bound Ω(t + p log p/ log log p).

UR - http://www.scopus.com/inward/record.url?scp=84927949869&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84927949869&partnerID=8YFLogxK

U2 - 10.1007/3-540-36108-1_20

DO - 10.1007/3-540-36108-1_20

M3 - Conference contribution

AN - SCOPUS:84927949869

SN - 3540000739

SN - 9783540000730

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 295

EP - 310

BT - Distributed Computing - 16th International Conference, DISC 2002, Proceedings

A2 - Malkhi, Dahlia

PB - Springer Verlag

T2 - 16th International Conference on Distributed Computing, DISC 2002

Y2 - 28 October 2002 through 30 October 2002

ER -