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 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 Theta (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 (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 Omega (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).