Asynchronous Consensus and Byzantine Protocols in Faulty Environments

Abstract

A consensus protocol enables a system of $n$ aynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes can only die, malicious processes can also send false messages. We investigate consensus protocols that terminate within finite time with probability 1 under certain assumptions on the behavior of the system. With fail-stop processes, we show that $\lceil (n + 1)/2 \rceil$ correct processes are necessary and sufficient to reach agreement. In the malicious case, we show that $\lceil (2n + 1)/3 \rceil$ correct processes are necessary and sufficient to reach agreement. This is contrasted with a recent result that there is no consensus protocol for the fail-stop case that always terminates within a bounded number of steps, even if only one process can fail. We also investigate the possibility of reliable broadcast (Byzantine Agreement) in an asynchronous system. We define the notion of Asynchronous Byzantine Agreement, and show that $\lceil (2n + 1)/3 \rceil$ correct processes are necessary and sufficient to reach Asynchronous Byzantine Agreement.