Consensus is the most critical and mathematically nuanced foundation of distributed computing. When multiple independent nodes must agree on a single value, state transition, or transaction order in an asynchronous network subject to arbitrary delays, packet drops, and machine crashes, naive coordination fails.
From the impossibility proof of Fischer, Lynch, and Paterson (FLP) to Leslie Lamport’s Paxos, Diego Ongaro’s Raft, and modern Byzantine consensus protocols, consensus algorithms guarantee linearizable state replication.
This module covers:
- FLP Impossibility & Partially Synchronous Models: Why deterministic asynchronous consensus is impossible in the presence of even a single unannounced crash, and how real systems overcome this via randomized election timers and partial synchrony ().
- Paxos Foundations: Phase 1a/1b (Prepare/Promise) and Phase 2a/2b (Accept/Accepted), dueling proposers, and Multi-Paxos steady-state optimization.
- Raft Quorum Invariants: Leader election, term numbers, log replication, commit rules, and formal safety proofs.
- Crash Fault Tolerance (CFT) vs. Byzantine Fault Tolerance (BFT): Why CFT requires nodes to tolerate crash failures, while BFT requires nodes to tolerate malicious or arbitrary failures.