distributed consensus algorithms

**Distributed Consensus Algorithms** are **protocols that enable multiple nodes in a distributed system to agree on a single value or sequence of values despite node failures and network partitions** — consensus is the foundational primitive for building reliable distributed systems including databases, coordination services, and blockchain networks. **The Consensus Problem:** - **Agreement**: all non-faulty nodes must decide on the same value — once a value is decided, the decision is irrevocable - **Validity**: the decided value must have been proposed by some node — the algorithm cannot fabricate values - **Termination**: all non-faulty nodes must eventually decide — liveness guarantee that prevents indefinite blocking - **FLP Impossibility**: Fischer, Lynch, and Paterson proved that deterministic consensus is impossible in an asynchronous system with even one crash failure — practical algorithms circumvent this with timeouts, randomization, or partial synchrony assumptions **Paxos Algorithm:** - **Roles**: proposers suggest values, acceptors vote on proposals, learners discover decided values — a single node can serve multiple roles simultaneously - **Phase 1 (Prepare)**: proposer sends Prepare(n) with proposal number n to a majority of acceptors — acceptors promise not to accept proposals numbered less than n and return any previously accepted value - **Phase 2 (Accept)**: if the proposer receives promises from a majority, it sends Accept(n, v) where v is the highest-numbered previously accepted value (or the proposer's own value) — acceptors accept if they haven't promised to a higher-numbered proposal - **Multi-Paxos**: optimizes repeated consensus decisions by electing a stable leader that skips Phase 1 — amortizes leader election cost over many consensus instances, reducing round trips from 2 to 1 per decision **Raft Algorithm:** - **Leader Election**: nodes start as followers, transition to candidates after an election timeout, and request votes from peers — a candidate receiving votes from a majority becomes leader for the current term - **Log Replication**: the leader appends client commands to its log and replicates entries to followers via AppendEntries RPCs — an entry is committed when replicated to a majority of nodes - **Safety Guarantees**: only nodes with up-to-date logs can be elected leader (election restriction), committed entries are never lost (leader completeness), and the log is never inconsistent (log matching property) - **Understandability**: Raft was explicitly designed for understandability — its decomposition into leader election, log replication, and safety makes it significantly easier to implement correctly than Paxos **Byzantine Fault Tolerance (BFT):** - **Byzantine Failures**: nodes may behave arbitrarily (crash, send conflicting messages, collude) — requires 3f+1 nodes to tolerate f Byzantine failures vs. 2f+1 for crash failures - **PBFT (Practical BFT)**: Castro and Liskov's protocol uses a three-phase commit (pre-prepare, prepare, commit) with 3f+1 replicas — achieves consensus in 2 round trips with O(n²) message complexity - **Blockchain Consensus**: Nakamoto consensus (Bitcoin) uses proof-of-work to achieve probabilistic BFT in a permissionless setting — sacrifices finality for open participation - **HotStuff**: linear-complexity BFT protocol using threshold signatures — reduces message complexity from O(n²) to O(n), adopted by Meta's Diem (Libra) blockchain **Practical Implementations:** - **ZooKeeper (ZAB)**: atomic broadcast protocol similar to Paxos — provides distributed coordination primitives (locks, barriers, leader election) used by Kafka, HBase, and Hadoop - **etcd (Raft)**: distributed key-value store powering Kubernetes cluster coordination — implements Raft with snapshotting, log compaction, and membership changes - **CockroachDB**: uses Raft consensus per data range for strongly consistent distributed SQL — thousands of independent Raft groups coordinate data across nodes - **Google Spanner**: combines Paxos with TrueTime (GPS-synchronized clocks) for globally consistent transactions — externally consistent reads without coordination using timestamp ordering **Performance Considerations:** - **Latency**: consensus requires at minimum one round trip to a majority — cross-datacenter Paxos/Raft adds 50-200ms per decision due to WAN latency - **Throughput**: batching multiple proposals into a single consensus round amortizes overhead — Multi-Paxos with batching achieves 100K+ decisions/second on modern hardware - **Flexible Paxos**: relaxes the requirement that prepare and accept quorums must both be majorities — any two quorums that intersect suffice, allowing optimization for read-heavy or write-heavy workloads **Consensus algorithms are the backbone of modern distributed infrastructure — every strongly consistent distributed database, every coordination service, and every blockchain ultimately relies on some form of consensus to ensure that distributed nodes agree on a shared state despite failures.**