Efficient agreement on bounded-degree networks

Piotr Berman, Juan A. Garay

    Research output: Contribution to journalConference articlepeer-review

    1 Scopus citations


    The distributed consensus problem requires n correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. The authors show how to achieve consensus on a bounded-degree network in the presence of O(n/log n) faulty processors in time O(n). Improvement on previous results is achieved, which implies that consensus can be reached in this setting in time Ω(n3).

    Original languageEnglish (US)
    Pages (from-to)188-191
    Number of pages4
    JournalProceedings of the International Conference on Parallel Processing
    StatePublished - 1989
    EventProceedings of the 1989 International Conference on Parallel Processing - University Park, PA, USA
    Duration: Aug 8 1989Aug 12 1989

    All Science Journal Classification (ASJC) codes

    • Hardware and Architecture

    Cite this