TY - GEN
T1 - Optimal early stopping in distributed consensus
AU - Berman, Piotr
AU - Garay, Juan A.
AU - Perry, Kenneth J.
N1 - Publisher Copyright:
© 1992, Springer Verlag. All rights reserved.
PY - 1992
Y1 - 1992
N2 - The Distributed Consensus problem involves n processors each of which holds an initial binary value. At most t processors may be faulty and ignore any protocol (even behaving maliciously), yet it is required that the non-faulty processors eventually agree on a value that was initially held by one of them. This paper presents consensus protocols that tolerate arbitrary faults, are early-stopping (i.e., run for a number of rounds proportional to the number of faults f that actually occur during their execution), and are optimal in various measures. Our first contribution is an early-stopping consensus protocol that is simultaneously optimal in round complexity (i.e., min(t+1, f+2) rounds) and number of processors (i.e., n > 3t). This settles a long-standing open question [DRS, 1982]. These bounds were not known to be attainable even with the use of authentication. Since consensus is not attainable with n ≤ 3t we provide a definitive answer to the problem of early-stopping consensus. Previous protocols for this problem that achieved round optimality required n = Ω(t2) [C, DRS], n > 6t [MW] and n > 4t [BGP]. Instrumental in achieving this result is the new safe message reconstruction technique, which we expect to be of broader applicability. The previous protocol is round- and processor-optimal, but not efficient. Our second contribution is a pair of optimal early-stopping consensus protocols that use messages of constant size. No previously existing early-stopping protocol, whether exactly or only asymptotically optimal in some measures, has used messages of constant size. The only other existing early-stopping protocol with constant-sized messages requires n = Ω(t2) [C]. Finally, we indicate how to extend one of the previous protocols to be optimal in total bit (and message) complexity and number of processors. This is the first protocol that is both optimal in these measures and early-stopping.
AB - The Distributed Consensus problem involves n processors each of which holds an initial binary value. At most t processors may be faulty and ignore any protocol (even behaving maliciously), yet it is required that the non-faulty processors eventually agree on a value that was initially held by one of them. This paper presents consensus protocols that tolerate arbitrary faults, are early-stopping (i.e., run for a number of rounds proportional to the number of faults f that actually occur during their execution), and are optimal in various measures. Our first contribution is an early-stopping consensus protocol that is simultaneously optimal in round complexity (i.e., min(t+1, f+2) rounds) and number of processors (i.e., n > 3t). This settles a long-standing open question [DRS, 1982]. These bounds were not known to be attainable even with the use of authentication. Since consensus is not attainable with n ≤ 3t we provide a definitive answer to the problem of early-stopping consensus. Previous protocols for this problem that achieved round optimality required n = Ω(t2) [C, DRS], n > 6t [MW] and n > 4t [BGP]. Instrumental in achieving this result is the new safe message reconstruction technique, which we expect to be of broader applicability. The previous protocol is round- and processor-optimal, but not efficient. Our second contribution is a pair of optimal early-stopping consensus protocols that use messages of constant size. No previously existing early-stopping protocol, whether exactly or only asymptotically optimal in some measures, has used messages of constant size. The only other existing early-stopping protocol with constant-sized messages requires n = Ω(t2) [C]. Finally, we indicate how to extend one of the previous protocols to be optimal in total bit (and message) complexity and number of processors. This is the first protocol that is both optimal in these measures and early-stopping.
UR - http://www.scopus.com/inward/record.url?scp=33748117259&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748117259&partnerID=8YFLogxK
U2 - 10.1007/3-540-56188-9_15
DO - 10.1007/3-540-56188-9_15
M3 - Conference contribution
AN - SCOPUS:33748117259
SN - 9783540561880
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 221
EP - 237
BT - Distributed Algorithms - 6th International Workshop, WDAG 1992, Proceedings
A2 - Segall, Adrian
A2 - Zaks, Shmuel
PB - Springer Verlag
T2 - 6th International Workshop on Distributed Algorithms, WDAG 1992
Y2 - 2 November 1992 through 4 November 1992
ER -