Distributed Consensus Protocols is the family of algorithms that enable a group of distributed processes to agree on a single value or sequence of decisions despite individual process failures, message delays, and network partitions — the foundational problem of distributed systems whose solution enables everything from replicated databases (etcd, CockroachDB), distributed coordination services (ZooKeeper), blockchain, and fault-tolerant storage systems to function correctly. The correctness of consensus algorithms (safety: all nodes agree on the same value; liveness: agreement is eventually reached) is the bedrock of distributed system reliability.

The Consensus Problem

• N processes propose values → all must agree on ONE value.
• Safety: No two processes decide differently.
• Liveness: All processes eventually decide.
• CAP Theorem: Distributed systems can guarantee at most 2 of: Consistency, Availability, Partition Tolerance.
• FLP Impossibility: In asynchronous systems with any faults, perfect consensus is impossible → real protocols require timing assumptions or probabilistic guarantees.

Paxos

• Lamport (1989/1998): The foundational consensus algorithm.
• Two phases:
• Phase 1 (Prepare/Promise): Proposer sends Prepare(n) → acceptors promise to reject ballots < n and return highest accepted value.
• Phase 2 (Accept/Accepted): Proposer sends Accept(n, v) → acceptors accept if no higher ballot seen → send Accepted to learners.
• Quorum: Majority (N/2 + 1) must respond → tolerates minority failures.
• Multi-Paxos: Elect leader once → run Phase 2 for each decision → efficient repeated consensus.
• Limitation: Complex to implement correctly, tricky edge cases, hard to understand → led to Raft.

Raft

• Ongaro & Ousterhout (2014): Designed for understandability.
• Leader election: Candidates request votes → majority wins → becomes leader for a term.
• Log replication: Leader receives client request → appends to log → replicates to followers → commit when majority acknowledge.
• Safety: Committed entries never lost → leader has all committed entries.
• Term: Monotonically increasing epoch → stale leaders detected by higher term numbers.

Raft Election

All start as Followers
    ↓ (election timeout, no heartbeat received)
Candidate: Vote for self, send RequestVote to all
    ↓ (receive majority votes)
Leader: Send heartbeats, replicate log
    ↓ (network partition, stale term)
Follower: Revert to follower if higher term seen

Paxos vs. Raft

Byzantine Fault Tolerance (BFT)

• Crash fault tolerance (Paxos/Raft): Processes crash but don't send incorrect messages.
• Byzantine fault: Faulty process can send arbitrary, contradictory, or malicious messages.
• PBFT (Practical Byzantine Fault Tolerance): Tolerates f Byzantine failures with 3f+1 replicas → 3 phases (pre-prepare, prepare, commit) → O(n²) messages.
• Use: Blockchain (early), safety-critical systems, adversarial environments.
• Modern BFT: HotStuff (used in Facebook Diem blockchain) → O(n) messages via threshold signatures.

etcd and Raft in Practice

• etcd: Distributed key-value store built on Raft → used by Kubernetes as cluster state store.
• 3-node or 5-node etcd cluster → tolerates 1 or 2 failure → maintains consensus.
• Kubernetes: All cluster state (pods, services, configmaps) stored in etcd → every kubectl command → etcd Raft consensus.

Performance and Latency

• Consensus round-trip: Leader → majority quorum → commit: 2 network RTTs = ~2 ms (datacenter).
• Throughput: etcd: ~10,000 transactions/sec (single cluster).
• WAN Paxos: Google Spanner global consensus: ~10 ms (cross-continent RTT).
• Optimization: Leader batching, pipelining commits, group commit → 100× throughput improvement.

Consensus in Databases

• CockroachDB: Raft per range (64 MB shard) → each shard independently replicated.
• Google Spanner: Paxos per tablet → globally distributed consistent transactions.
• TiKV: Raft for multi-raft key-value store → Rust implementation.

Distributed consensus protocols are the algorithmic bedrock of reliable distributed computing — every fault-tolerant database, configuration management system, container orchestration platform, and blockchain relies on consensus to transform a collection of individual, failure-prone machines into a system that collectively behaves as a single reliable entity, making consensus algorithms among the most practically consequential computer science contributions of the past four decades, studied in every serious distributed systems course and implemented in the infrastructure that underlies cloud computing at global scale.