Tight Bounds on the Round Complexity of Distributed 1-Solvable Tasks
DOI:
https://doi.org/10.7146/dpb.v20i377.6609Resumé
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 the authors in 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 this number 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 and binary monotone consensus 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.
Downloads
Publiceret
Citation/Eksport
Nummer
Sektion
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.