Tight bounds on the round complexity of distributed 1-solvable tasks

AbstractA distributed task T is 1-solvable if there exists a protocol that solves it in the presence of (at most) one crash failure. A precise characterization of the 1-solvable tasks was given by Biran et al. (1990). In this paper we determine the number of rounds of communication that are required, in the worst case, by a protocol which 1-solves a given 1-solvable task T for n processors. We define the radius R(T) of T, and show that if R(T) is finite, then the number of rounds is Θ(logn R(T)); more precisely, we give a lower bound of log(n − 1) R(T), and an upper bound of 2 + ⌈log(n − 1) R(T)⌉. The upper bound implies, for example, that each of the following tasks: renaming, order preserving renaming (Attiya et al, 1990) and binary monotone consensus (Biran et al., 1990) can be solved in the presence of one fault in 3 rounds of communications. All previous protocols that 1-solved these tasks required Ω(n) rounds. The result is also generalized to tasks whose radii are not bounded, e.g., the approximate consensus and its variants (Dolev et al., 1986; Biran et al., 1990)