distributed consensus

**Distributed Consensus** is the **fundamental problem of getting multiple distributed nodes to agree on a single value or sequence of values** — despite node failures and network partitions, enabling fault-tolerant distributed systems. **The Consensus Problem** - N nodes must agree on a value. - Properties required: - **Safety**: All nodes that decide, decide the same value. - **Liveness**: All non-faulty nodes eventually decide. - **Validity**: The decided value was proposed by some node. - **FLP Impossibility (1985)**: No deterministic algorithm guarantees consensus in asynchronous networks with even one faulty process. - Practical solution: Assume partial synchrony (bounded message delay) or use randomization. **Paxos (Lamport, 1989)** Two phases: **Phase 1 (Prepare)**: - Proposer sends Prepare(n) to majority of acceptors. - Acceptors respond with Promise(n) and any previous accepted value. **Phase 2 (Accept)**: - Proposer sends Accept(n, v) — v = highest previously accepted value or new proposal. - Majority of acceptors accept → value decided. - **Property**: Any value decided by quorum A is preserved by any future quorum B (overlap of ≥ 1). - **Challenge**: Complex, many corner cases — "Paxos is famously difficult to implement correctly." **Raft (Ongaro & Ousterhout, 2014)** Designed for understandability: **Leader Election**: - Nodes start as Followers. - Election timeout → becomes Candidate → sends RequestVote RPC. - Majority vote → becomes Leader. - Leader sends heartbeats to prevent new elections. **Log Replication**: - All writes go to leader. - Leader appends to log → sends AppendEntries to followers. - Committed when majority acknowledge → apply to state machine. **Properties**: - **Term numbers**: Monotonically increasing, detect stale leaders. - **Log matching**: If two logs have same entry at same index, they're identical up to that point. **Fault Tolerance** - Tolerates (N-1)/2 failures for N nodes. - 3 nodes: Tolerates 1 failure. 5 nodes: Tolerates 2 failures. **Real-World Implementations** - **etcd**: Raft-based distributed key-value store (Kubernetes config backend). - **CockroachDB**: Raft per-range for distributed SQL. - **Consul**: Service discovery with Raft. - **Zookeeper**: ZAB protocol (Paxos-like) for distributed coordination. Distributed consensus is **the theoretical foundation of reliable distributed systems** — every fault-tolerant database, distributed cache, and cluster coordinator relies on consensus protocols to maintain consistency in the presence of failures, making Raft the essential algorithm for modern cloud infrastructure.