an asynchronous [(n - 1)/3]-resilient consensus protocol
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.
asynchronicity consensus systems process message presence probability paper matching lower bound context resilience