1985/10/01 by Gabriel Bracha, Sam Toueg · 509 citations
Computer Science · Mathematics · #Artificial intelligence #Asynchronous communication #Asynchronous system #Bounded function #Byzantine fault tolerance #Class (philosophy) #Computer network #Computer science #Consensus #Distributed computing #Distributed systems and fault tolerance #Fault tolerance #Mathematics #Multi-agent system #Petri Nets in System Modeling #Process (computing) #Protocol (science) #Quantum Byzantine agreement #Telecommunications #Theoretical computer science #Uniform consensus
paper · pdf · doi:10.1145/4221.214134
published in Journal of the ACM 32(4), 824-840 (Association for Computing Machinery)
openalex publication_date 1985/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
A consensus protocol enables a system of n asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes that can only die and malicious processes that can also send false messages. The class of asynchronous systems with fair schedulers is defined, and consensus protocols that terminate with probability 1 for these systems are investigated. With fail-stop processes, it is shown that ⌈( n + 1)/2⌉ correct processes are necessary and sufficient to reach agreement. In the malicious case, it is shown that ⌈(2 n + 1)/3⌉ correct processes are necessary and sufficient to reach agreement. This is contrasted with an earlier result, stating 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. The possibility of reliable broadcast (Byzantine Agreement) in asynchronous systems is also investigated. Asynchronous Byzantine Agreement is defined, and it is shown that ⌈(2 n + 1)/3⌉ correct processes are necessary and sufficient to achieve it.