The Do-All problem in broadcast networks

Research output: Contribution to conferencePaperpeer-review

10 Scopus citations


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 Ω(t+p√t) of work. We develop an optimal deterministic algorithm for the channel with collision detection performing only the minimum work Θ(t+p√t). Another algorithm is given for the channel without collision detection, it performs work O(t+p√t+p · min{f,t}), where f < p 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.

Original languageEnglish (US)
Number of pages10
StatePublished - 2001
Externally publishedYes
Event20th Annual ACM Symposium on Principles of Distributed Computing - Newport, Rhode Island, United States
Duration: Aug 26 2001Aug 29 2001


Conference20th Annual ACM Symposium on Principles of Distributed Computing
Country/TerritoryUnited States
CityNewport, Rhode Island


  • Adversary
  • Distributed algorithm
  • Fail-stop failures
  • Independent tasks
  • Lower bound
  • Multiple-access channel

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'The Do-All problem in broadcast networks'. Together they form a unique fingerprint.

Cite this