The Byzantine Generals Problem
Leslie Lamport, Robert Shostak, Marshall Pease1982ACM TOPLAS 1982
Read it on lamport.azurewebsites.net(opens in a new tab)Why this one
Crash faults are polite: a machine stops answering and the rest of the system can route around the silence. Byzantine faults are hostile: a participant can send different lies to different peers and still look healthy. That one change is why this paper belongs next to Paxos Made Simple and Impossibility of Distributed Consensus with One Faulty Process, but also why it points forward to Practical Byzantine Fault Tolerance and Bitcoin. Read this after Paxos Made Simple if consensus currently feels like leader election plus retries. The lesson is not that every service needs Byzantine agreement. Most do not. The lesson is to name your trust model before you design the protocol. If clients, replicas, networks, or operators can equivocate, then majority vote is not the same primitive anymore, and the cost shows up as extra replicas, rounds, and signed evidence.
What to take away
- Byzantine agreement needs at least 3m plus 1 generals to tolerate m traitors in the oral messages model.
- The hard case is equivocation: one faulty node can tell different honest nodes different stories.
- Signed messages change the cost model by making lies transferable as evidence.
Reads with
- Paxos Made Simple
shows the crash fault consensus model this paper deliberately hardens
- Impossibility of Distributed Consensus with One Faulty Process
proves even polite failures can block consensus in asynchronous systems
- Practical Byzantine Fault Tolerance
turns the model into a working replicated state machine protocol