Distributed Consensus: Multi-Paxos, Raft Invariants & Byzantine Fault Tolerance

Consensus is the pinnacle challenge of distributed systems. At its core, consensus solves a seemingly simple question: How can a group of independent computers agree on a state transition or log sequence over an unreliable network where packets can be arbitrarily delayed, reordered, duplicated, or dropped, and where individual machines can crash at any instant?

Without consensus, building reliable distributed databases, distributed locking services, and linearizable coordination primitives is mathematically impossible.

This lesson explores the foundations of consensus: the FLP Impossibility Theorem, Leslie Lamport’s Paxos, Diego Ongaro’s Raft, and the rigorous mathematical divergence between Crash Fault-Tolerance (CFT) and Byzantine Fault-Tolerance (BFT).

1. Problem and Motivation

Consider an etcd or ZooKeeper cluster managing leader leases for a distributed database.

• If the primary database locks a row, writes an update, and commits, all replicas must agree on that exact sequence of operations.
• If a temporary network switch partition splits a 5-node cluster into two groups ($2$ nodes and $3$ nodes), both sides cannot be allowed to elect independent leaders and commit concurrent writes (Split-Brain catastrophe).

Why can’t we simply use two-phase commit (2PC)?

• 2PC is a blocking protocol: If the coordinator crashes while participants are in the PREPARED state holding locks, the entire system blocks indefinitely. 2PC guarantees atomicity, but fails to provide availability in the presence of node crashes.

True consensus protocols provide both Safety (nothing bad happens; nodes never decide on conflicting values) and Non-blocking Liveness (eventually, all healthy nodes decide).

2. Mental Model & Architectural Taxonomy

SYSTEM ARCHITECTURE BLUEPRINTDISTRIBUTED SYSTEMS

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. Phase 1: Leader Lease / Prepare (Run once per term) & Phase 2: Steady-State Log Append (Fast Path)

Establishes the ingress and structural boundary across Phase 1: Leader Lease / Prepare (Run once per term) & Phase 2: Steady-State Log Append (Fast Path): 1a. Proposer sends Prepare(proposal_number = n) 1b. Acceptors return Promise(highest_v_seen, highest_n_seen) Acceptors pledge never to accept any future proposal < n Requires MAJORITY quorum (f + 1 of 2f + 1 nodes); 2a. Leader sends Accept(instance_id, slot_i, value = v) 2b. Acceptors return Accepted(instance_id, slot_i) In Multi-Paxos, Phase 1 is skipped during steady-state Commits in exactly 1 RTT over local network!; Proposer A issues Prepare(10) → Majority promises.

Architectural Invariant: Fix: Randomized backoff election timers (used in Raft).

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Raft 5 Core Safety Invariants

Coordinates core data-plane execution and state transitions through Raft 5 Core Safety Invariants: 1. Election Safety: At most one leader elected per term; 2. Leader Append-Only: Leader never overwrites its own log; 3. Log Matching: Matching (index, term) implies identical logs.

Architectural Invariant: Election Rule: Candidate must have more up-to-date log than voter!.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. Crash Fault-Tolerant (CFT) vs. Byzantine (BFT) & CFT (Raft / Paxos)

Enforces durability, state convergence, and output verification across Crash Fault-Tolerant (CFT) vs. Byzantine (BFT) & CFT (Raft / Paxos): Tolerates: Crash-stop; Nodes: N = 2f + 1; Quorum: f + 1 3 nodes tolerate 1 crash.

Architectural Invariant: Quorum: 2f + 1 4 nodes tolerate 1 traitor.

The Landscape of Consensus Protocols

                                  Consensus Protocols
                                           │
                 ┌─────────────────────────┴─────────────────────────┐
                 ▼                                                   ▼
       Crash Fault-Tolerant (CFT)                       Byzantine Fault-Tolerant (BFT)
      (Nodes crash-stop or crash-recover)              (Nodes can act maliciously / lie)
                 │                                                   │
        Nodes: N = 2f + 1                                   Nodes: N = 3f + 1
       Quorum: Q = f + 1                                   Quorum: Q = 2f + 1
                 │                                                   │
       ┌─────────┴─────────┐                               ┌─────────┴─────────┐
       ▼                   ▼                               ▼                   ▼
  Multi-Paxos            Raft                            PBFT              Tendermint
(Chubby, Spanner)     (etcd, TiKV)                   (Castro-Liskov)      (Cosmos, Web3)

3. The FLP Impossibility Theorem (1985)

In 1985, researchers Fischer, Lynch, and Paterson published their landmark paper:

“Impossibility of Distributed Consensus with One Faulty Process”

The Theorem

In a purely asynchronous distributed system, no deterministic consensus protocol can guarantee both safety and liveness in the presence of even a single unannounced crash failure.

Why FLP Holds:

In an asynchronous network, message delay is unbounded. If Node A does not hear from Node B, it is mathematically impossible to differentiate between two realities:

1. Node B has crashed.
2. Node B is running perfectly fine, but the network link is experiencing high latency.

An adversary can delay packets in a pathological cycle, continually flipping nodes between indecisive states forever.

How Real Systems Bypass FLP

Practical protocols (Paxos, Raft) make two engineering relaxations:

1. Partial Synchrony: They assume that while the network can experience arbitrary delays temporarily, there exists an unknown Global Stabilization Time (GST) after which message transmission delays are bounded by $\Delta$.
2. Randomization: Raft uses randomized election timeouts ($150\text{ ms}-300\text{ ms}$) to break deterministic symmetry and prevent dueling candidate livelocks.

4. Single-Decree Paxos & Multi-Paxos

Invented by Turing Award laureate Leslie Lamport, Paxos operates in two distinct phases:

Phase 1: Prepare / Promise (Leader Election / Lease)

1. 1a. Prepare: A Proposer selects a unique, monotonically increasing proposal number $n$ and broadcasts $\text{Prepare}(n)$ to a majority of Acceptors.
2. 1b. Promise: If $n>\text{highest\_promised\_n}$ on an Acceptor:
   • Acceptor sets $\text{highest\_promised\_n}=n$.
   • Acceptor replies $\text{Promise}(n,v_{\text{highest}},n_{\text{highest}})$, pledging never to accept any future proposal numbered less than $n$.

Phase 2: Accept / Accepted (Value Commitment)

1. 2a. Accept: If the Proposer receives promises from a majority of Acceptors ($f+1$):
   • It sets value $v=v_{\text{highest}}$ (the value from the promise with the highest proposal number), or its own desired value if no acceptor reported a prior value.
   • Proposer broadcasts $\text{Accept}(n,v)$ to the Acceptors.
2. 2b. Accepted: If $n\ge \text{highest\_promised\_n}$, the Acceptor accepts $(n,v)$ and broadcasts $\text{Accepted}(n,v)$ to the Proposer and Learners.

Multi-Paxos Optimization

Single-Decree Paxos requires 2 full Round Trips (RTTs) for every single log slot. Multi-Paxos amortizes Phase 1 across thousands of log entries: once a Proposer wins Phase 1, it acquires a stable leader lease and executes only Phase 2 (Accept/Accepted) for subsequent log entries, committing updates in 1 RTT.

Raft’s Five Core Safety Invariants & Log Matching Proof

Ongaro and Ousterhout (2014) decomposed Multi-Paxos into Raft, structuring replicated log consensus around five formal safety invariants that hold at all times across arbitrary crash-recoveries and network partitions:

1. Election Safety: At most one leader can be elected in a given term $T$. (Guaranteed because each server votes at most once per term and winning requires a strict majority $Q=\lfloor N/2\rfloor +1$).
2. Leader Append-Only: A leader never overwrites or deletes entries in its own log; it only appends new entries.
3. Log Matching: If two logs contain an entry with the same index $k$ and term $T$, then the logs store the identical command at index $k$ and are byte-for-byte identical in all preceding entries $[\mathrm{1..}k-1]$.
   • Proof by Induction: By Election Safety, at most one leader creates entries in term $T$, and it assigns each index at most once (base match at index $k$). On every AppendEntries RPC for index $k$, the leader transmits (prevLogIndex = k - 1, prevLogTerm), and the follower rejects the append unless its local entry at $k-1$ matches prevLogTerm. By induction from $k-1$ down to index $1$, matching at $(k,T)$ forces the entire prefix $[\mathrm{1..}k]$ to match identically.
4. Leader Completeness: If a log entry is committed in term $T$, that entry will be present in the logs of the leaders for all higher-numbered terms $T^{\prime }>T$. (Enforced via the RequestVote up-to-date log comparison: lexicographically comparing (lastLogTerm, lastLogIndex) across intersecting commit and election majorities).
5. State Machine Safety: If a server has applied a log entry at index $k$ to its state machine, no other server will ever apply a different log entry for index $k$.

5. Mathematical Proof: CFT ($2f+1$) vs. BFT ($3f+1$)

5.1 Crash Fault-Tolerance (CFT) Quorum Derivation

Suppose a cluster of $N$ nodes must tolerate up to $f$ crash-stop failures:

• Liveness Bound: When $f$ nodes crash, the remaining $N-f$ healthy nodes must still form a valid quorum $Q$ and make progress: $$Q\le N-f$$
• Safety Bound (Quorum Intersection): To prevent two partitioned sub-clusters from electing competing leaders or committing conflicting log entries, any two quorums $Q_1,Q_2$ of size $Q$ must overlap by at least 1 node: $$|Q_1\cap Q_2|\ge 2Q-N\ge 1⟹2Q\ge N+1⟹Q\ge \frac{N+1}{2}$$

Combining both bounds ($\frac{N+1}{2}\le Q\le N-f$): $$\frac{N+1}{2}\le N-f⟹N+1\le 2N-2f⟹N\ge 2f+1$$

Setting minimal $N=2f+1$ gives $Q=f+1$:

• To tolerate $f=1$ crash: $N=2(1)+1=3\text{ nodes}$ ($Q=2$).
• To tolerate $f=2$ crashes: $N=2(2)+1=5\text{ nodes}$ ($Q=3$).

5.2 Byzantine Fault-Tolerance (BFT) Quorum Derivation

In an adversarial Byzantine network, up to $f$ nodes are malicious traitors that can either remain completely silent (simulating a crash) or equivocate (send conflicting signed vote $A$ to Quorum $Q_1$ and vote $B$ to Quorum $Q_2$):

• Liveness Bound: Because up to $f$ Byzantine nodes may refuse to respond at all, the system cannot wait for more than $N-f$ replies: $$Q_{\text{BFT}}\le N-f$$
• Safety Bound (Honest Witness in Every Quorum Intersection): Any two quorums $Q_1$ and $Q_2$ of size $Q_{\text{BFT}}$ intersect in at least $2Q_{\text{BFT}}-N$ nodes. Because up to $f$ nodes inside that intersection could be equivocating traitors, the intersection must contain at least $f+1$ nodes so that at least $(f+1)-f=1$ honest, non-faulty witness refuses to certify conflicting decisions: $$2Q_{\text{BFT}}-N\ge f+1$$

Substituting $Q_{\text{BFT}}\le N-f$: $$2(N-f)-N\ge f+1⟹N-2f\ge f+1⟹N\ge 3f+1$$

Equivalently, among $N-f$ received responses, up to $f$ may be forged lies, leaving $(N-f)-f=N-2f$ guaranteed honest responses that must strictly outvote $f$ traitors ($N-2f>f⟹N\ge 3f+1$). The minimal Byzantine quorum size for $N=3f+1$ is: $$Q_{\text{BFT}}=N-f=2f+1$$

• To tolerate $f=1$ traitor: $N=3(1)+1=4\text{ nodes}$ ($Q_{\text{BFT}}=3$).
• To tolerate $f=2$ traitors: $N=3(2)+1=7\text{ nodes}$ ($Q_{\text{BFT}}=5$).

6. Production TypeScript Simulation: Single-Decree Paxos Engine

Below is an executable simulation demonstrating Paxos Phase 1 and Phase 2 consensus, showing how acceptors force competing proposers to converge safely:

export interface PromiseResponse {
  accepted: boolean;
  highestAcceptedN: number | null;
  highestAcceptedV: string | null;
}

export class PaxosAcceptor {
  public highestPromisedN = 0;
  public highestAcceptedN: number | null = null;
  public highestAcceptedV: string | null = null;

  constructor(public readonly id: string) {}

  // Phase 1b: Evaluate Prepare
  public onPrepare(n: number): PromiseResponse {
    if (n > this.highestPromisedN) {
      this.highestPromisedN = n;
      return {
        accepted: true,
        highestAcceptedN: this.highestAcceptedN,
        highestAcceptedV: this.highestAcceptedV,
      };
    }
    return { accepted: false, highestAcceptedN: null, highestAcceptedV: null };
  }

  // Phase 2b: Evaluate Accept
  public onAccept(n: number, v: string): boolean {
    if (n >= this.highestPromisedN) {
      this.highestPromisedN = n;
      this.highestAcceptedN = n;
      this.highestAcceptedV = v;
      return true;
    }
    return false;
  }
}

export class PaxosProposer {
  constructor(
    public readonly id: string,
    public readonly acceptors: PaxosAcceptor[]
  ) {}

  public async propose(proposalNumber: number, initialValue: string): Promise<string> {
    const majority = Math.floor(this.acceptors.length / 2) + 1;

    // --- PHASE 1: PREPARE ---
    let promiseCount = 0;
    let highestPriorN: number | null = null;
    let chosenValue = initialValue;

    for (const acceptor of this.acceptors) {
      const resp = acceptor.onPrepare(proposalNumber);
      if (resp.accepted) {
        promiseCount++;
        if (resp.highestAcceptedN !== null) {
          if (highestPriorN === null || resp.highestAcceptedN > highestPriorN) {
            highestPriorN = resp.highestAcceptedN;
            chosenValue = resp.highestAcceptedV!; // Must adopt existing value!
          }
        }
      }
    }

    if (promiseCount < majority) {
      throw new Error(`PrepareRejected: Only received ${promiseCount}/${majority} promises`);
    }

    // --- PHASE 2: ACCEPT ---
    let acceptedCount = 0;
    for (const acceptor of this.acceptors) {
      if (acceptor.onAccept(proposalNumber, chosenValue)) {
        acceptedCount++;
      }
    }

    if (acceptedCount < majority) {
      throw new Error(`AcceptRejected: Only received ${acceptedCount}/${majority} accepts`);
    }

    return chosenValue; // Consensus successfully reached
  }
}

async function runDemo(): Promise<void> {
  console.log("=== Consensus Algorithms: Paxos Proposer & Acceptor Simulation ===");
  const acceptors = [new PaxosAcceptor("acc-1"), new PaxosAcceptor("acc-2"), new PaxosAcceptor("acc-3")];
  const proposerA = new PaxosProposer("prop-A", acceptors);
  const proposerB = new PaxosProposer("prop-B", acceptors);
  console.log("Initialized Multi-Acceptor Paxos Quorum (N=3, Majority=2)");

  const committed1 = await proposerA.propose(10, "CommitTransaction#101");
  console.log(`[Round n=10] Proposer A committed value: '${committed1}'`);

  // Competing Proposer B attempts to propose a different value with higher n=20
  const committed2 = await proposerB.propose(20, "ConflictingTransaction#202");
  console.log(`[Round n=20] Competing Proposer B forced to adopt chosen value: '${committed2}'`);
}

runDemo();

Simulation Execution Output & State Transitions

=== Consensus Algorithms: Paxos Proposer & Acceptor Simulation ===
Initialized Multi-Acceptor Paxos Quorum (N=3, Majority=2)
[Round n=10] Proposer A committed value: 'CommitTransaction#101'
[Round n=20] Competing Proposer B forced to adopt chosen value: 'CommitTransaction#101'

7. Open-Source Implementation Analysis

A. etcd & TiKV: Raft Engine

• etcd/raft (v3.5+): Written in Go, etcd isolates the deterministic Raft state machine from network and disk I/O. Applications pass incoming network messages into RawNode.Step() and consume ready state transitions (Ready.Entries, Ready.HardState, Ready.Messages), persisting Entries and HardState via fsync to the local WAL before dispatching outbound network frames.
• TiKV Multi-Raft (v7.x+): Partitioned distributed KV engines split keyspaces into $96\text{ MB}$ Regions, each governed by an independent Raft group, combining ReadIndex heartbeats and LeaseRead bounded clock leases to serve linearizable reads without writing read-only entries to disk.

B. Google Spanner: Multi-Paxos with TrueTime

• Spanner partitions tables into Directories/Splits, and each split is replicated across geographic zones via long-lived Multi-Paxos groups with 10-second disjoint leader leases.
• Spanner integrates Multi-Paxos with TrueTime (GPS and rubidium atomic clock hardware API returning $[t_{\text{earliest}},t_{\text{latest}}]$). Leaders overlap Paxos replication with a $2ϵ$ commit-wait window ($ϵ\approx 1-7\text{ ms}$) to guarantee global external consistency across continents.

8. Failure Modes & Operational War Stories

War Story: The Dueling Proposer Livelock

• Incident: An early Multi-Paxos implementation ran two active proposers without a stable leader lease or randomized backoff.
• Failure: Proposer 1 issued Prepare(10). Before it could send Accept, Proposer 2 sent Prepare(20), causing acceptors to update their promise to $20$. When Proposer 1 sent Accept(10), acceptors rejected it. Proposer 1 immediately retried with Prepare(30), preempting Proposer 2’s Accept(20).
• Outcome: Both proposers continually outbid each other in a frantic loop, generating millions of network packets per second while zero log entries were ever committed (Livelock—demonstrating FLP in action).
• Mitigation: Introduced stable leader leases coupled with Pre-Vote / randomized exponential backoff timers ($150\text{ ms}-300\text{ ms}$) before re-proposing, ensuring one proposer cleanly completes Phase 2 before peers challenge leadership.

9. Design Alternatives, Trade-offs & Operational Decision Guide

10. Hands-on Operational Drills

1. Simulate Split-Vote Value Adoption in Paxos: Modify the TypeScript simulation so Acceptors acc-1 and acc-2 accept "A" at $n=10$ while acc-3 misses Phase 2. Next, partition acc-1 offline and have Proposer B run Phase 1 with $n=20$ against {acc-2, acc-3}. Verify that acc-2’s promise forces Proposer B to adopt "A".
2. Verify Split Quorums in an Even-Sized 4-Node CFT Cluster: Model a 4-node CFT cluster ($N=4⟹Q=\lfloor 4/2\rfloor +1=3$). Show why $N=4$ tolerates only $f=1$ crash (worse availability than $N=3$ because 4 hardware nodes can fail instead of 3, and a $2\text{ vs }2$ partition halts both sides).

11. Summary & Architectural Decision Checklist

• FLP Impossibility mandates choosing between blocking safety and probabilistic/partially synchronous liveness: always ensure consensus nodes run with randomized election timeouts ($\gg 10\times \text{RTT}$) so transient network jitter does not trigger dueling elections.
• Deploy odd cluster sizes ($N=3$ or $N=5$) for Crash Fault-Tolerant coordination (etcd, Apache ZooKeeper, TiKV): $N=4$ requires $Q=3$ and survives only $f=1$ failure while increasing write quorum latency and failure surface.
• Reserve BFT ($N\ge 3f+1$) strictly for multi-organization or untrusted trust domains; inside a single private cloud VPC protected by SPIFFE mTLS, CFT protocols deliver $3\times -10\times$ higher throughput without $O(N^2)$ all-to-all signature verification.

12. Authoritative References & Version Context

• Version & Implementation Baseline: Architectural claims reflect etcd v3.5 (go.etcd.io/etcd/raft/v3), TiKV v7.5 Multi-Raft engine, Apache ZooKeeper v3.9 (ZAB protocol), and CometBFT / Tendermint Core v0.38.
• Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2), 374–382.
• Lamport, L. (2001). Paxos Made Simple. ACM SIGACT News, 32(4), 51–58.
• Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm (Extended Version). Proceedings of USENIX ATC ‘14, 305–319.
• Castro, M., & Liskov, B. (1999). Practical Byzantine Fault Tolerance. Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI ‘99), 173–186.
• etcd Authors. etcd/raft Library Design & Linearizable ReadIndex Documentation.