The Complexity of Almost-Optimal Simultaneous Coordination

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.