JavaScript is disabled for your browser. Some features of this site may not work without it.
An Asynchronous [(n-1)/3]-Resilient Consensus Protocols

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-01Publisher
Cornell University
Subject
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