Distributed Consensus

Formally, distributed consensus requires four properties:

• Termination: every non-faulty node eventually decides.
• Validity: the decided value was proposed by some node.
• Integrity: each node decides at most once.
• Agreement: no two non-faulty nodes decide differently.

FLP showed that in a purely asynchronous network with even one possible crash failure, no deterministic algorithm can satisfy all four. Every real protocol works around this — Paxos and Raft sacrifice termination during pathological scenarios (split votes), guaranteeing termination only under partial synchrony (timing eventually behaves).

Eric Brewer's 2000 conjecture, proved by Gilbert & Lynch in 2002: in the presence of a network Partition, you must choose between Consistency (linearizability) and Availability.

The PACELC extension: when there's no partition, you still trade Latency vs Consistency. Strong consistency requires consensus rounds, which always cost RTTs.

Read more: Paxos deep dive · Raft deep dive · Leader election internals.

Zab is the protocol behind Apache ZooKeeper. Like Multi-Paxos, it has a leader and a log; like Raft, it requires strict prefix matching. Zab is older than Raft and has a similar shape, with one specialty: FIFO client order preservation within a session, even across leader changes.

# Zab phases:
1. Leader election (FastLeaderElection algorithm)
2. Discovery — new leader collects highest accepted state from quorum
3. Synchronization — leader pushes its log to followers
4. Broadcast — steady-state log replication (one RTT per write)

# Each transaction has a globally ordered "zxid" (epoch + counter).
# This zxid maps directly to Raft's (term, index) tuple.

Apache Kafka used ZooKeeper for cluster metadata until KRaft (Kafka Raft) replaced it in 2022. Most other Zab usage is legacy (Hadoop, HBase).

EPaxos (Moraru et al., SOSP 2013) breaks the leader bottleneck: any replica can commit non-conflicting commands in 1 RTT. Conflicting commands need an extra round to resolve dependencies.

# EPaxos commit flow:
1. Client sends command to nearest replica R
2. R sends PreAccept to all peers, including its set of "interfering" past commands
3. If a fast quorum (~3N/4) all return identical interference set:
   commit in 1 RTT (fast path)
   Else: do an Accept round to settle dependencies (slow path, 2 RTTs)

# Benefits: no leader bottleneck; reads scale linearly with replicas
# Costs: complex dependency tracking; slower under contention

EPaxos has theoretical advantages (better tail latency, no leader hotspot) but few production users — the implementation complexity is significant. CockroachDB explored it; ended up sticking with Raft.

People conflate these. They solve different problems:

• 2PC (two-phase commit): atomic commit across N participants. Blocking under coordinator failure. Used for distributed transactions.
• 3PC (three-phase commit): 2PC + a pre-commit phase to avoid coordinator-failure blocking. Vulnerable to network partitions; rarely used.
• Consensus (Paxos, Raft): replicated state machine. Tolerates failures via majority quorum. Used to replicate the same state to multiple nodes.

Modern distributed databases combine them: per-shard consensus (Raft) for replication, plus 2PC across shards for transactions that span them. Spanner's "Paxos + 2PC" is the canonical example.

Crash-fault consensus assumes nodes either work or stop. BFT consensus assumes some nodes can be malicious: lie, equivocate, send conflicting messages to different peers. This requires 3f+1 nodes to tolerate f Byzantine failures — a 50% jump from the 2f+1 of crash-fault systems.

BFT is essential for permissionless blockchains where any node could be hostile. Inside a single organization with trusted operators, crash-fault Raft is enough — and 50% cheaper.

Consensus orders writes within one group. To order events globally — across many Raft groups, or across regions — you need timestamps. The standard tools:

• Lamport timestamps: simple counter incremented on send/receive. Provides causal order, not real time.
• Vector clocks: per-node counters. Detects concurrent events but grows with nodes.
• Hybrid Logical Clocks (HLC): physical time + logical counter. Bounded skew; works without atomic clocks. Used by CockroachDB, MongoDB.
• TrueTime: bounded clock uncertainty from atomic clocks + GPS. Used by Spanner. Allows external consistency without coordination.

Combining timestamps with consensus is what makes distributed transactions tractable. Spanner = Paxos + 2PC + TrueTime. CockroachDB = Raft + parallel commits + HLC. Both achieve serializable transactions across thousands of shards.

Need to replicate state across nodes?
├─ No → just use a database, you don't need consensus directly
├─ Yes →
│  ├─ Within a single organization (trusted)?
│  │  ├─ Yes → Raft (etcd-io/raft, hashicorp/raft)
│  │  └─ No  → BFT (Tendermint, HotStuff)
│  └─ Cross-shard transactions?
│     ├─ No  → per-shard Raft is enough
│     └─ Yes → 2PC + per-shard Raft (CockroachDB pattern)
│              OR Spanner-style 2PC + TrueTime
└─ Just need leader election (no log)?
   └─ Use etcd or ZooKeeper as a primitive

The right answer 95% of the time is "use a Raft library; don't write consensus from scratch." It is genuinely hard to get right; even simple bugs can violate safety in subtle, partition-dependent ways.

Foundational papers and textbooks for going deeper:

• Lamport, "Paxos Made Simple" (2001) — the readable Paxos explanation. Read after the 1998 paper if you want the full proof.
• Ongaro & Ousterhout, "In Search of an Understandable Consensus Algorithm" (2014) — the Raft paper. Plus Ongaro's PhD thesis for the long-form version including snapshot, membership change, and TLA+ spec.
• Chandra, Griesemer, Redstone, "Paxos Made Live" (2007) — Google's experience implementing Chubby. The single best read on what's actually hard.
• Liskov & Cowling, "Viewstamped Replication Revisited" (2012) — a clearer presentation of VSR than the 1988 original.
• Howard, "Distributed Consensus Revised" (2019, PhD thesis) — Flexible Paxos and a unifying view of the family.
• Castro & Liskov, "Practical Byzantine Fault Tolerance" (1999) — PBFT, the foundation of every BFT protocol since.
• Kleppmann, "Designing Data-Intensive Applications" (2017) — chapters 8 and 9 are the best textbook treatment.