The Weak Byzantine Generals Problem

1983/07/01 by Leslie Lamport, L. Lamport · 5 citations
Computer Science · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Logic, Reasoning, and Knowledge

paper · pdf · doi:10.1145/2402.322398

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
• 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