The Complexity of Almost-Optimal Coordination

Abstract

The problem of fault-tolerant coordination is fundamental in distributed computing. In the past, researchers have considered the complexity of achieving optimal simultaneous coordination under various failure assumptions. This paper studies the complexity of achieving simultaneous coordination in synchronous systems in the presence of send/receive omission failures. It had been shown earlier that achieving optimal simultaneous coordination in these systems requires NP-hard local computation. In this paper, we study almost-optimal coordination, which requires processors to coordinate within a constant additive or multiplicative number of rounds of the coordination time of an optimal protocol. We show that achieving almost-optimal coordination also requires NP-hard computation.