The Weak Byzantine Generals Problem

1983/07/01 by Leslie Lamport, L. Lamport · 219 citations
Computer Science · #Archaeology #Byzantine architecture #Citation #Complexity and Algorithms in Graphs #Computer science #Computer security #Cryptography and Data Security #History #Library science #Logic, Reasoning, and Knowledge #World Wide Web

paper · pdf · doi:10.1145/2402.322398

published in Journal of the ACM 30(3), 668-676 (Association for Computing Machinery)

openalex publication_date 1983/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

Abstract

The Byzantine Generals Problem requires processes to reach agreement upon a value even though some of them may fad. It is weakened by allowing them to agree upon an "incorrect" value if a failure occurs. The transaction eormmt problem for a distributed database Js a special case of the weaker problem. It is shown that, like the original Byzantine Generals Problem, the weak version can be solved only ff fewer than one-third of the processes may fad. Unlike the onginal problem, an approximate solution exists that can tolerate arbaranly many failures.

Citations

• Reaching Agreement in the Presence of Faults

Cited by

• Lower Bounds on Implementing Robust and Resilient Mediators
• Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks
• Dealing With Curious Players in Secure Networks
• The AnyLog Edge Data Fabric
• Distributed Ledger Privacy: Ring Signatures, Möbius and CryptoNote
• Flow: Separating Consensus and Compute -- Execution Verification
• Byzantine Consensus in the Common Case
• Multiparty Symmetric Sum Types
• The Byzantine generals strike again
• Efficient quantum detectable weak Byzantine agreement with optimal fault-tolerant bound
• Finding Traitors in Secure Networks Using Byzantine Agreements
• Offline Scaling of IoT Devices in IOTA Blockchain. [europepmc]
• Quantum blockchain based on asymmetric quantum encryption and a stake vote consensus algorithm. [europepmc]

Related

• All Byzantine Agreement Problems are Expensive
• Impossibility of distributed consensus with one faulty process
• Beyond One Third Byzantine Failures
• Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
• New Efficient Error-Free Multi-Valued Consensus with Byzantine Failures