Distributed Consensus and Paxos
Stub. Consensus in asynchronous systems and the FLP impossibility result; the Byzantine generals problem and consensus with oral messages (the OM(m) algorithm) and signed messages; failure-detector-based consensus (the P and S detectors); and Paxos.
The central impossibility and the central practical workaround. FLP proves that no deterministic asynchronous consensus protocol can tolerate even one crash failure — which is why every practical protocol either assumes partial synchrony, uses randomization, or (Paxos) accepts that safety always holds but liveness only holds “eventually.” Covers the synchronous Byzantine-fault case first (the OM(m) recursive protocol for oral messages, and the simpler signed-message variant), then the asynchronous crash-fault case via failure detectors — the P (perfect) and S (eventually strong) detectors that let Chandra-Toueg-style consensus route around FLP — and finally Paxos itself as the protocol used in practice.
Outline (TODO — flesh out each)
- Consensus in asynchronous systems — the FLP impossibility result
- The Byzantine generals problem — the no-traitor case, interactive consistency
- Consensus with oral messages — an impossibility result, the OM(m) algorithm
- Consensus using signed messages
- Failure detectors — solving consensus with P and with S
- Paxos