Bounding work and communication in robust cooperative computation

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


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).

Original languageEnglish (US)
Title of host publicationDistributed Computing - 16th International Conference, DISC 2002, Proceedings
EditorsDahlia Malkhi
PublisherSpringer Verlag
Number of pages16
ISBN (Print)3540000739, 9783540000730
StatePublished - 2002
Externally publishedYes
Event16th International Conference on Distributed Computing, DISC 2002 - Toulouse, France
Duration: Oct 28 2002Oct 30 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Conference on Distributed Computing, DISC 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Bounding work and communication in robust cooperative computation'. Together they form a unique fingerprint.

Cite this