distributed consensus algorithm
**Distributed Consensus Algorithms** are the **fundamental protocols that enable multiple nodes in a distributed system to agree on a single value (or sequence of values) despite node failures, network partitions, and message delays — providing the consistency guarantees that underpin replicated databases, distributed lock services, leader election, and configuration management in every production distributed system from Google Spanner to etcd to Apache ZooKeeper**.
**The Consensus Problem**
N nodes must agree on a value. Requirements:
- **Agreement**: All non-faulty nodes decide the same value.
- **Validity**: The decided value was proposed by some node (no invented values).
- **Termination**: All non-faulty nodes eventually decide (liveness).
- **Fault Tolerance**: Correct operation despite up to f failed nodes (crash or Byzantine). For crash failures: requires 2f+1 nodes to tolerate f failures.
**Paxos (Lamport, 1989)**
The foundational consensus protocol:
- **Prepare Phase**: Proposer sends Prepare(n) with proposal number n to all acceptors. Acceptors promise not to accept proposals with numbers < n and return any previously accepted value.
- **Accept Phase**: If a majority of acceptors respond, proposer sends Accept(n, v) where v is the previously accepted value with highest number (or the proposer's own value if none). Acceptors accept if they haven't promised a higher number.
- **Consensus Reached**: When a majority of acceptors accept the same (n, v), value v is chosen.
Multi-Paxos extends single-decree Paxos to a log of decisions: a stable leader drives consensus for each log entry without repeating the Prepare phase, achieving one round-trip per decision in the common case.
**Raft (Ongaro & Ousterhout, 2014)**
Designed for understandability (Paxos is notoriously difficult to implement correctly):
- **Leader Election**: Nodes are followers by default. If no heartbeat from leader within election timeout, a follower becomes candidate and requests votes. Wins with majority.
- **Log Replication**: Leader appends client commands to its log, replicates entries to followers. Entry is committed when replicated to a majority. Committed entries are applied to state machine.
- **Safety**: Only candidates with the most up-to-date log can win election — guarantees no committed entry is lost.
Raft is used in: etcd (Kubernetes backing store), CockroachDB, TiKV, Consul, and dozens of production systems.
**Performance Characteristics**
| Metric | Paxos/Raft | Impact |
|--------|-----------|--------|
| Latency (LAN) | 1-5 ms per decision | Limited by disk fsync + network RTT |
| Latency (WAN) | 50-200 ms | Limited by cross-datacenter RTT |
| Throughput | 10K-100K decisions/sec | Batching amortizes per-decision overhead |
| Availability | Requires majority (3/5, 2/3) | Tolerates minority failures |
**Byzantine Fault Tolerance (BFT)**
Paxos and Raft assume crash failures (nodes stop but don't lie). BFT protocols (PBFT, HotStuff, Tendermint) tolerate Byzantine failures (nodes may send arbitrary/malicious messages). Require 3f+1 nodes for f Byzantine failures. Used in blockchain consensus, military/aerospace systems.
Distributed Consensus is **the theoretical and practical foundation of reliable distributed systems** — the algorithmic guarantee that a collection of unreliable machines can provide the illusion of a single, consistent, fault-tolerant service that never loses acknowledged data.