Asymptotically optimal distributed consensus: Extended abstract

Piotr Berman, Juan A. Garay

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

    35 Scopus citations


    The Distributed Consensus problem requires correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. In this paper we present a protocol that achieves consensus with n>4t total processors using 2t+2 rounds of communication and messages of size 1. This is the first protocol in which all three parameters are simultaneously within a constant factor from their optima. Subsequently, we modify it to obtain a family of equally resilient protocols which use t(1 + 1/d) rounds and O(2d) message size, improving on previous results. Finally, we show that the first protocol can be adapted very efficiently to run on bounded-degree networks, so that consensus can be reached in the presence of O(n/log n) faulty processors in time O(n). It improves on the previous result, which implied that consensus can be reached in this setting in time Θ(n3).

    Original languageEnglish (US)
    Title of host publicationAutomata, Languages and Programming - 16th International Colloquium, Proceedings
    EditorsMariangiola Dezani-Ciancaglini, Simonetta Ronchi Della Rocca, Giorgio Ausiello
    PublisherSpringer Verlag
    Number of pages15
    ISBN (Print)9783540513711
    StatePublished - 1989
    Event16th International Colloquium on Automata, Languages and Programming, 1989 - Stresa, Italy
    Duration: Jul 11 1989Jul 15 1989

    Publication series

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


    Other16th International Colloquium on Automata, Languages and Programming, 1989

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • Computer Science(all)


    Dive into the research topics of 'Asymptotically optimal distributed consensus: Extended abstract'. Together they form a unique fingerprint.

    Cite this