The Complexity of Almost-Optimal Simultaneous Coordination

Rida Bazzi, G. Neiger

Research output: Contribution to journalArticlepeer-review


The problem of fault-tolerant coordination is fundamental in distributed computing. In the past researchers have considered achieving simultaneous coordination under various failure assumptions. It has been shown that doing so optimally in synchronous systems with send/receive omission failures requires NP-hard local computation. This paper studies almost-optimal simultaneous coordination, which requires processors to coordinate within a constant additive or multiplicative number of rounds of the coordination time of an optimal protocol. It shows that achieving such coordination also requires NP-hard computation.

Original languageEnglish (US)
Pages (from-to)308-321
Number of pages14
JournalAlgorithmica (New York)
Issue number3
StatePublished - Mar 1997


  • Common knowledge
  • Fault tolerance
  • NP-completeness
  • Processor knowledge
  • Simultaneous coordination

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'The Complexity of Almost-Optimal Simultaneous Coordination'. Together they form a unique fingerprint.

Cite this