The Problem of Distributed Consensus

In a single-server system, deciding the truth is trivial: the CPU core executes instructions sequentially, the operating system kernel coordinates locking, and the local disk acts as the authoritative log.

In a distributed system, there is no shared memory, no shared physical clock, and communication occurs over an asynchronous, unreliable network where packets can be delayed, duplicated, or dropped.

The Distributed Consensus Problem is the fundamental challenge of getting a group of independent, failure-prone computers to agree on a single value, sequence of actions, or state transitions.

---

1. The Replicated State Machine (RSM) Model

Consensus is almost never solved for an isolated, one-off value. In real-world infrastructure (such as Kubernetes etcd, Apache Kafka KRaft, CockroachDB, and Google Cloud Spanner), consensus is used to build a Replicated State Machine (RSM).

The State Machine Invariant:

If two identical, deterministic state machines start in the same initial state and apply the exact same sequence of log commands in the exact same order, they are guaranteed to end in the exact same final state.

---

2. The 4 Formal Invariants of Consensus

To be mathematically correct under the asynchronous crash-recovery model, any consensus algorithm must satisfy four non-negotiable invariants:

---

3. The FLP Impossibility Result (Fischer, Lynch, Paterson 1985)

In 1985, Fischer, Lynch, and Paterson published one of the most famous proofs in computer science:

$\text{In an asynchronous network, no deterministic consensus protocol can guarantee both Safety and Liveness if even a single node is permitted to crash.}$

How Practical Systems Circumvent FLP:

Real-world consensus algorithms (Paxos, Raft, ZAB) circumvent FLP by making weak timing assumptions (Partial Synchrony):

• They use heartbeat timeouts and randomized election timers ($150\text{ms}-300\text{ms}$).
• If the network experiences temporary chaos, the cluster temporarily pauses progress (sacrificing liveness temporarily) to ensure that safety (zero data corruption) is NEVER violated.

---

4. Paxos vs Raft: Why the Industry Standardized on Raft

For two decades following Leslie Lamport's 1998 paper "The Part-Time Parliament", Paxos was the undisputed academic standard for consensus.

However, Classic Paxos had a critical flaw: it was notoriously difficult to understand and implement in software.

Why Raft Won the Cloud-Native Ecosystem:

In 2014, Diego Ongaro and John Ousterhout designed Raft with a primary design goal: Understandability.

1. Decomposed into Independent Subproblems: Raft splits consensus into three completely distinct phases: Leader Election, Log Replication, and Safety Invariants.
2. Strong Leader Invariant: Log entries only flow in one direction—from the Leader to Followers. Followers never propose writes directly.
3. Adoption: Today, etcd (Kubernetes), CockroachDB, TiKV, HashiCorp Consul, and Kafka KRaft all run production Raft consensus engines.

---

5. Code Deep-Dive: Deterministic State Machine Engine

The heart of an RSM is absolute determinism. If any node executes non-deterministic operations (such as Date.now(), Math.random(), or unseeded UUIDs) during log application, nodes will diverge permanently.

---

6. Production Failure Postmortem: The Non-Deterministic State Machine Divergence

Incident Overview:

In 2019, an open-source distributed SQL database suffered silent data corruption across secondary nodes during automated schema migration transactions.

What Happened:

1. A developer added a default column creation feature: created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP().
2. When the consensus leader proposed the log entry ADD_COLUMN created_at, the log entry contained the raw SQL string rather than a pre-computed deterministic timestamp.
3. Node 1 evaluated CURRENT_TIMESTAMP() at 14:00:00.100.
4. Node 2 (which processed the log entry $40\text{ms}$ later over the network) evaluated CURRENT_TIMESTAMP() at 14:00:00.140.
5. When a downstream query ran SELECT * WHERE created_at = '14:00:00.100', Node 1 returned the row while Node 2 returned empty set $⟹$ Consensus State Divergence.

Key Lesson:

• Consensus logs must only contain pure, deterministic inputs. All timestamps, random seeds, and external parameters must be evaluated and fixed by the leader before writing the log entry to the cluster.

---

7. Chapter Summary & Consensus Invariant Checklist