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.