Hall of FameLeslie Lamport, Robert Shostak, Marshall Pease198252 min readpaperadvanced
The Byzantine Generals Problem
Summary
This paper defines the Byzantine Generals Problem, where loyal generals must agree on a plan despite traitors sending conflicting information. It proves that with oral messages, a solution exists if and only if more than two-thirds of generals are loyal, but with unforgeable signed messages, it's solvable for any number of traitors.
- The Byzantine Generals Problem models reliable systems coping with components sending conflicting information to different parts.
- With oral messages, a solution requires N > 3m, meaning more than two-thirds of generals must be loyal (N = total, m = traitors).
- Specifically, no solution exists for three generals with a single traitor using only oral messages.
- Unforgeable signed messages allow for solutions to the Byzantine Generals Problem for any number of generals and possible traitors.
This foundational paper is essential for anyone designing or understanding fault-tolerant distributed systems, as it establishes fundamental limits and solutions for consensus in the presence of arbitrary failures.
9/10
