Byzantine Generals Problem
The foundational puzzle of decentralized agreement.
The Byzantine Generals Problem (BGP) is a logical dilemma formulated by Leslie Lamport, Robert Shostak, and Marshall Pease in 1982. It describes a scenario where several divisions of the Byzantine army are camped outside an enemy city. Each division is led by a general, and all must decide on a common plan: to attack or retreat. To succeed, all honest generals must agree and execute the same plan. However, some generals may be traitors who send conflicting messages to cause failure. BGP illustrates the fundamental challenge of ensuring consistency in decentralized networks where nodes may be faulty or adversarial.
graph LR
Center["Byzantine Generals Problem"]:::main
Pre_distributed_systems["distributed-systems"]:::pre --> Center
click Pre_distributed_systems "/terms/distributed-systems"
Center --> Child_byzantine_fault_tolerance["byzantine-fault-tolerance"]:::child
click Child_byzantine_fault_tolerance "/terms/byzantine-fault-tolerance"
Rel_consensus_mechanisms["consensus-mechanisms"]:::related -.-> Center
click Rel_consensus_mechanisms "/terms/consensus-mechanisms"
Rel_proof_of_work["proof-of-work"]:::related -.-> Center
click Rel_proof_of_work "/terms/proof-of-work"
Rel_digital_signatures["digital-signatures"]:::related -.-> Center
click Rel_digital_signatures "/terms/digital-signatures"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧒 Erkläre es wie einem 5-Jährigen
🏰 It's the story of how to trust a group when you know some people are lying.
🤓 Expert Deep Dive
## Technical Deep Dive: Lamport's Proof
In the 1982 paper, it was shown that with only 3 generals (A, B, C) where one is a traitor (C), consensus is impossible.
### The Failure Scenario
1. General A sends 'Attack' to B and C.
2. General C (traitor) says 'Retreat' to B.
3. General B now sees 'Attack' from A and 'Retreat' from C. He cannot know who is the traitor.
This simple proof necessitates the $3f+1$ rule for non-cryptographic BFT. With Digital Signatures, a general cannot lie about what another general said, which drastically simplifies the solution space.