Distributed Consensus

Distributed Consensus — algorithms that ensure multiple nodes in a distributed system agree on a single value or sequence of values, despite network failures and delays, forming the foundation of reliable distributed systems.

The Consensus Problem

• N nodes must agree on a value (e.g., "who is the leader?" or "what is the next log entry?")
• Must handle: Network partitions, message delays, node crashes
• Impossible to solve with guaranteed termination in asynchronous systems (FLP impossibility) — practical algorithms use timeouts

Raft (Most Popular Today)

• Designed for understandability (vs Paxos complexity)
• Leader Election: Nodes start as followers. If no heartbeat received → become candidate → request votes → majority wins → become leader
• Log Replication: Leader receives client requests, appends to log, replicates to followers. Committed when majority acknowledge
• Safety: Only nodes with up-to-date logs can become leader

Paxos

• Original consensus algorithm (Lamport, 1989)
• Proposer, Acceptor, Learner roles
• Correct but famously difficult to understand and implement
• Multi-Paxos: Extension for sequence of values (replicated log)

Real-World Usage

• etcd: Raft-based key-value store (used by Kubernetes)
• ZooKeeper: ZAB protocol (Paxos variant). Coordination service
• CockroachDB, TiKV: Raft for distributed transactions
• Google Spanner: Paxos for global consensus

Distributed consensus is the hardest problem in distributed systems — but it's what makes databases, orchestrators, and cloud infrastructure reliable.