Fast consensus in networks of bounded degree

Piotr Berman, Juan A. Garay

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

    5 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. In this paper we focus on consensus in networks that are not completely interconnected, following the work of Dwork et al. [DPPU]. In such a context, complete consensus among all the correct processors is not possible and some exceptions must be allowed. We first show how to achieve consensus in the butterfly network using O(t +logn loglogn) one bit parallel transmission steps, while tolerating the asymptotically optimal number of faulty processors and asymptotically minimal number of exceptions. This result considerably improves upon our previous protocol, in particular it replaces the running time of O(n logn loglogn) with an asymptotically optimal one. As in [DPPU], we can decrease the number of exceptions to O(t) by using additional links, while maintaining the same running time. The protocol is derived from a consensus protocol for complete networks that is interesting in its own right. It achieves Distributed Consensus with optimal number of processors, asymptotically optimal total bit transfer and nearly optimal number of rounds, with better constant factors than previously published results.

    Original languageEnglish (US)
    Title of host publicationDistributed Algorithms - 4th International Workshop, Proceedings
    EditorsJan van Leeuwen, Nicola Santoro
    PublisherSpringer Verlag
    Number of pages13
    ISBN (Print)9783540540991
    StatePublished - 1991
    Event4th International Workshop on Distributed Algorithms, WDAG 1990 - Bari, Italy
    Duration: Sep 24 1990Sep 26 1990

    Publication series

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


    Other4th International Workshop on Distributed Algorithms, WDAG 1990

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Fast consensus in networks of bounded degree'. Together they form a unique fingerprint.

    Cite this