TIGHT BOUNDS ON THE ROUND COMPLEXITY OF DISTRIBUTED 1-SOLVABLE TASKS

A distributed task T is 1-solvable if there exists a protocol that sol ves it in the presence of(at most) one crash failure. A precise charac terization of the 1-solvable tasks was given by Biran et al. (1990). I n this paper we determine the number of rounds of communication that a re 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), a nd an upper bound of 2 + [log((n-1)) R(T)]. The upper bound implies, f or example, that each of the following tasks: renaming, order preservi ng 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 re quired Omega (n) rounds. The result is also generalized to tasks whose radii are not bounded, e.g., the approximate consensus and its varian ts (Dolev et al., 1986; Biran et al., 1990).