An asynchronous [(n - 1)/3]-resilient consensus protocol

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<n/5. We improve this to t<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.