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

A 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 in [BMZ]. 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 this number is Θ(log n 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 ([ABDKPR]) and binary monotone consensus [BMZ] 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 [DLPSW, BMZ].