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

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.