Optimal early stopping in distributed consensus

Piotr Berman, Juan A. Garay, Kenneth J. Perry

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    28 Scopus citations

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationDistributed Algorithms - 6th International Workshop, WDAG 1992, Proceedings
    EditorsAdrian Segall, Shmuel Zaks
    PublisherSpringer Verlag
    Pages221-237
    Number of pages17
    ISBN (Print)9783540561880
    DOIs
    StatePublished - 1992
    Event6th International Workshop on Distributed Algorithms, WDAG 1992 - Haifa, Israel
    Duration: Nov 2 1992Nov 4 1992

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume647 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other6th International Workshop on Distributed Algorithms, WDAG 1992
    Country/TerritoryIsrael
    CityHaifa
    Period11/2/9211/4/92

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'Optimal early stopping in distributed consensus'. Together they form a unique fingerprint.

    Cite this