Asynchronous byzantine agreement protocols (Q1091131)

A consensus protocol enables a system of n asynchronous processes, some of them faulty, to reach agreement. Both the processes and the message system are capable of cooperating to prevent the correct processes from reaching decision. A protocol is t-resilient if in the presence of up to t faulty processes it reaches agreement with probability 1. Byzantine processes are faulty processes can be deviate arbitrarily from the protocol; Fail-Stop processes can just stop participating in it. In a recent paper, t-resilient randomized consensus protocols were presented for \(t<n/5\). We improve this to \(t<n/3\), thus matching the known lower bound on the number of correct processes necessary for consensus. The protocol uses a general technique in which the behavior of the Byzantine processes is restricted by the use of a broadcast protocol that filters some of the messages. The apparent behavior of the byzantine processes, filtered by the broadcast protocol, is similar to that of fail-stop processes. Plugging the broadcast protocol as a communicating primitive into an agreement protocol for fail-stop processes gives the result. This technique, of using broadcast protocols to reduce the power of the faulty processes and then using them as communication primitives in algorithms designed for weaker failure models, was used successfully in other contexts.