Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. An Asynchronous [(n-1)/3]-Resilient Consensus Protocols

An Asynchronous [(n-1)/3]-Resilient Consensus Protocols

File(s)
84-590.pdf (711.6 KB)
84-590.ps (233.86 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6430
Collections
Computer Science Technical Reports
Author
Bracha, Gabriel
Abstract

A consensus protocol enables a system of $n$ asynchronous processes, some of them malicious, to reach agreement. No assumptions are made on the behaviour of the processes and the message system; both are capable of colluding to prevent the correct processes from reaching decision. A protocol is $t$-resilient if in the presence of up to $t$ malicious processes it reaches agreement with probability 1. In a recent paper, $t$-resilient consensus protocols were presented for $t less than n / 5$. We improve this to $t less than n / 3$, thus matching the lower bound on the number of correct processes necessary for consensus. The protocol restricts the behaviour of the malicious processes to that of merely fail-stop processes, which makes it interesting in other contexts.

Date Issued
1984-01
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84-590
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance