Towards optimal distributed consensus

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

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

    91 Scopus citations


    In a distributed consensus protocol all processors (of which t may be faulty) are given (binary) initial values; after exchanging messages all correct processors must agree on one of them. The quality of a protocol is measured here using as parameters the total number of processors n, number of rounds of message exchange r, and maximal message length m, with optima, respectively, of 3t + 1, t + 1, and 1. Although no known protocol is optimal in all these three aspects simultaneously, the protocols that take further steps in this direction are presented. The first protocol has n > 4t, r = t + 1, and polynomial message size. The second protocol has n > 3t, r = 3t + 3, and m = 2, and it is asymptotically optimal in all three quality parameters while using the optimal number of processors. Using these protocols as building blocks, families of protocols with intermediate quality parameters, offering better tradeoffs than previous results, are obtained. All the protocols work in polynomial time and have succinct descriptions.

    Original languageEnglish (US)
    Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
    PublisherPubl by IEEE
    Number of pages6
    ISBN (Print)0818619821, 9780818619823
    StatePublished - 1989
    Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
    Duration: Oct 30 1989Nov 1 1989

    Publication series

    NameAnnual Symposium on Foundations of Computer Science (Proceedings)
    ISSN (Print)0272-5428


    Other30th Annual Symposium on Foundations of Computer Science
    CityResearch Triangle Park, NC, USA

    All Science Journal Classification (ASJC) codes

    • Hardware and Architecture


    Dive into the research topics of 'Towards optimal distributed consensus'. Together they form a unique fingerprint.

    Cite this