Free lesson · System Design Fundamentals

Consensus Algorithms: Introduction

Medium10 min readsystem-designhlddistributed-systems

Lesson 21.1 - Consensus Algorithms: Introduction

The first lesson of Module 21.

Five generals surround an enemy city. They must agree on a single plan: attack at dawn, or retreat. Each general sends messengers to the other four with their vote. But some messengers might be captured (lost messages). Some generals might be traitors (Byzantine faults - sending "attack" to one general and "retreat" to another). If the generals don't reach consensus, some attack and some retreat - a divided force that gets destroyed.

This is the Byzantine Generals Problem (Lamport, 1982) - and it's a metaphor for every consensus problem in distributed systems. Replace "generals" with "database replicas." Replace "attack or retreat" with "is the current value of key X 'Alice' or 'Bob'?" Replace "messengers captured" with "network packets dropped." Replace "traitors" with "buggy nodes sending conflicting responses." The problem is identical: how do multiple independent agents agree on a single value when communication is unreliable and some agents might behave incorrectly?

What Is Consensus?

Consensus is the process of getting multiple distributed nodes to agree on a single value (or a single decision) despite failures. The agreed-upon value might be:

• Who is the leader? (leader election - 21.4)
• What is the committed value for key X? (replicated state machine)
• Which transaction should be applied next? (total order broadcast)
• Should we commit or abort this distributed transaction? (two-phase commit)
• Which server gets the distributed lock? (21.5)

A consensus algorithm must satisfy three properties:

1. Agreement: all non-faulty nodes decide on the same value. If Node A decides "Alice" and Node B decides "Bob," consensus has failed - the system is in an inconsistent state.

2. Validity: the decided value must have been proposed by some node. The algorithm can't invent a value that nobody proposed - it must choose from the options on the table.

3. Termination: every non-faulty node eventually decides. The algorithm can't run forever without reaching a decision - at some point, the nodes must commit to a value and move forward.

flowchart TD
    subgraph Proposals["PROPOSALS"]
        N1["Node 1\nproposes: 'Alice'"]
        N2["Node 2\nproposes: 'Bob'"]
        N3["Node 3\nproposes: 'Alice'"]
        N4["Node 4\nproposes: 'Bob'"]
        N5["Node 5\nproposes: 'Alice'"]
    end
    
    Consensus["CONSENSUS ALGORITHM\n\nExchanges messages.\nHandles failures.\nReaches agreement.\n\nMust satisfy:\n✅ Agreement (same value)\n✅ Validity (proposed value)\n✅ Termination (eventually decides)"]
    
    subgraph Decision["DECISION"]
        D["All non-faulty nodes\nagree: 'Alice'\n\n(3 of 5 proposed Alice\n→ majority wins)"]
    end
    
    Proposals --> Consensus --> Decision

    style Consensus fill:#fbbf24,stroke:#f59e0b,color:#000
    style Decision fill:#34d399,stroke:#10b981,color:#000

A diagram showing the consensus process. Five nodes each propose a value: three propose Alice, two propose Bob. The consensus algorithm exchanges messages between nodes, handles potential failures (dropped messages, crashed nodes), and reaches agreement. The decision: all non-faulty nodes agree on Alice. The algorithm satisfies three properties: Agreement - all nodes chose the same value (Alice). Validity - Alice was proposed by nodes 1, 3, and 5; the algorithm didn't invent it. Termination - the algorithm completed and produced a decision, rather than running forever. The majority (3 of 5) proposed Alice, so Alice wins - but this isn't a simple vote. The algorithm must handle scenarios where messages are lost, nodes crash mid-vote, or the network partitions the nodes into groups that can't communicate. The algorithm ensures that even in these failure scenarios, at most one value is chosen, all surviving nodes agree on it, and the decision is final.

Why Consensus Is Hard

Consensus sounds simple: "just vote and pick the majority." But three properties of distributed systems make it genuinely hard:

Problem 1: Nodes Can Crash at Any Time

A node can crash after proposing a value but before receiving the decision. It can crash after receiving the decision but before applying it. It can crash during the consensus algorithm itself - mid-vote. The algorithm must handle all these crash timings correctly: the remaining nodes must still reach consensus without the crashed node, and the crashed node must be able to recover and learn the decision when it comes back online.

Subtlety: a node that crashes and recovers must not "change its mind." If a node voted for "Alice" before crashing, it can't vote for "Bob" after recovery. This requires durable state - each node must persist its vote to disk (via WAL - M14.3) before sending it, so that recovery can reconstruct the node's pre-crash state.

Problem 2: Messages Can Be Lost, Delayed, or Reordered

The network is unreliable (19.1). A vote message from Node 1 to Node 3 might arrive in 1ms, 100ms, or never. A "commit" message might arrive at Node 2 before the "prepare" message (out of order). The algorithm can't assume that all messages arrive, arrive in order, or arrive within any time bound.

Subtlety: if Node 1 sends its vote to all other nodes but the message to Node 3 is lost, Node 3 hasn't received the vote. Does Node 1 re-send? How long does Node 3 wait before giving up? What if Node 3 concludes "Node 1 must be dead" (it's not - the message was just lost) and starts a new consensus round?

Problem 3: No Global Clock

Nodes can't use physical time to coordinate - clocks drift (20.1), and there's no way to say "all nodes must vote by 14:00:00.000" because each node's 14:00:00.000 is a different real-world instant. The algorithm must use message-based coordination (logical ordering - 20.2) rather than time-based coordination.

The FLP Impossibility Result

In 1985, Fischer, Lynch, and Paterson proved a result that sent shockwaves through distributed systems theory: in an asynchronous system where even one node can crash, no deterministic consensus algorithm can guarantee termination.

This is the FLP Impossibility - named after its authors. Let's break it down:

"Asynchronous system" means there's no upper bound on message delivery time. A message might take 1ms or 1 hour - the algorithm can't distinguish "slow message" from "lost message" from "crashed node." There are no timeouts (because timeouts require assumptions about message delivery time).

"Even one node can crash" means the algorithm must tolerate at least one failure.

"No deterministic algorithm can guarantee termination" means there exists a scenario where the algorithm runs forever without deciding. Not that it ALWAYS runs forever - just that there EXISTS a pathological execution where it does.

What FLP does NOT say:

FLP does NOT say consensus is impossible. It says deterministic consensus with guaranteed termination is impossible in a purely asynchronous model. Practical consensus algorithms (Paxos, Raft) get around FLP in three ways:

1. Randomization. Use random coin flips to break symmetry - the algorithm terminates with probability 1 (almost surely) even if not deterministically. Ben-Or's algorithm (1983) uses this approach.

2. Partial synchrony. Assume the network is eventually synchronous - messages are eventually delivered within some bound, even if that bound isn't known in advance. Paxos and Raft use this model: they rely on timeouts for liveness (electing a leader, detecting failures) while maintaining safety (never deciding on two different values) regardless of timing.

3. Failure detectors. Assume an oracle that eventually correctly identifies crashed nodes (even if it's initially wrong). Chandra-Toueg (1996) showed that consensus is solvable with unreliable failure detectors - detectors that might be temporarily wrong but are eventually correct.

The practical implication: FLP tells us that no consensus algorithm can guarantee progress in ALL network conditions. Real algorithms (Raft, Paxos) guarantee safety always (never decide on two different values) and liveness eventually (will terminate once the network stabilizes - messages eventually get through, a leader is eventually elected). During a sustained network partition or adversarial message scheduling, the algorithm may stall - but it never produces a wrong answer. Stalling is acceptable; data corruption is not.

The Consensus Landscape

Not all distributed agreement problems are equal. Different systems need different levels of agreement:

Strong Consensus (Agreement on Exact Value)

All nodes agree on the exact same value. Used for: leader election, distributed locks, replicated state machines, linearizable reads. Algorithms: Paxos, Raft, ZAB (ZooKeeper), Viewstamped Replication.

Cost: requires message exchange between a majority of nodes for every decision. Latency is at least one network round trip (propose → accept). Throughput is limited by the slowest majority member.

Eventual Convergence (Agreement Eventually)

Nodes may temporarily disagree but converge to the same value over time. Used for: replicated counters, collaborative editing, distributed caches, DNS propagation. Mechanisms: CRDTs (21.7), gossip protocols (21.6), last-writer-wins.

Cost: much lower than strong consensus - no coordination during writes. The cost is paid during reads (checking for conflicts) or in background reconciliation.

Coordination-Free (No Agreement Needed)

Operations are designed so that agreement is never required. Each node operates independently and the results are always compatible. Used for: commutative operations (increment/decrement counters), set union operations, append-only logs. Mechanism: CRDTs with mathematical properties that guarantee merge correctness.

Cost: the data structure must be carefully designed so that all operation orderings produce the same result. Not all data structures support this - only those with commutative, associative, and idempotent merge functions.

The Key Systems Built on Consensus

Every major distributed database or coordination service uses a consensus protocol internally. Understanding Paxos and Raft (the next two lessons) means understanding how ALL of these systems maintain consistency.

Two-Phase Commit: Consensus for Distributed Transactions

Before Paxos and Raft, the most common "consensus" mechanism was Two-Phase Commit (2PC) - a protocol for committing a transaction across multiple database nodes.

Phase 1 - Prepare: the coordinator sends a PREPARE message to all participants. Each participant checks whether it can commit (locks acquired, constraints satisfied, WAL written). If yes, it responds VOTE-COMMIT. If no, it responds VOTE-ABORT.

Phase 2 - Commit/Abort: if ALL participants voted COMMIT, the coordinator sends COMMIT to all participants. If ANY participant voted ABORT, the coordinator sends ABORT to all.

sequenceDiagram
    participant C as Coordinator
    participant P1 as Participant 1
    participant P2 as Participant 2
    participant P3 as Participant 3
    
    C->>P1: PREPARE
    C->>P2: PREPARE
    C->>P3: PREPARE
    P1->>C: VOTE-COMMIT ✅
    P2->>C: VOTE-COMMIT ✅
    P3->>C: VOTE-COMMIT ✅
    Note over C: All voted COMMIT →<br/>decide COMMIT
    C->>P1: COMMIT
    C->>P2: COMMIT
    C->>P3: COMMIT

A Two-Phase Commit sequence diagram. The coordinator sends PREPARE to three participants. Each participant checks if it can commit - verifying locks, constraints, and durability. All three vote COMMIT (they can commit). The coordinator sees all votes are COMMIT, so it decides COMMIT and sends the COMMIT message to all three participants. Each participant applies the transaction and releases locks. If even ONE participant had voted ABORT, the coordinator would have sent ABORT to all - the transaction is all-or-nothing across all participants. This is the simplest form of distributed transaction coordination.

The critical flaw of 2PC: the coordinator is a single point of failure. If the coordinator crashes after sending PREPARE but before sending COMMIT/ABORT, the participants are stuck - they've voted but don't know the decision. They hold locks on the data (to prevent other transactions from conflicting), waiting for the coordinator's decision. If the coordinator stays down for hours, the participants' locks are held for hours - blocking all other transactions on the affected data. This is the blocking problem of 2PC.

Three-Phase Commit (3PC) attempts to solve the blocking problem by adding a PRE-COMMIT phase, but it doesn't work correctly in the presence of network partitions (a partitioned participant might miss the PRE-COMMIT and make the wrong decision).

Paxos and Raft solve the blocking problem differently: they replicate the coordinator itself across multiple nodes using consensus. If the coordinator crashes, a new coordinator is elected from the replicas - the decision is never lost. This is why modern distributed databases use Raft or Paxos for transaction coordination instead of 2PC.

The Mental Model for This Module

The remaining lessons build on this foundation in a logical progression:

flowchart TD
    Consensus["21.1 Consensus Problem\n(the 'what')"]
    
    Paxos["21.2 Paxos\n(classical solution)"]
    Raft["21.3 Raft\n(understandable solution)"]
    
    Leader["21.4 Leader Election\n(built on consensus)"]
    Lock["21.5 Distributed Locks\n(built on consensus)"]
    
    Gossip["21.6 Gossip\n(eventual - no consensus)"]
    CRDT["21.7 CRDTs\n(convergence - no consensus)"]
    OT["21.8 OT\n(collaborative editing)"]
    
    Consensus --> Paxos & Raft
    Paxos & Raft --> Leader & Lock
    Consensus -.->|"alternatives to\nstrong consensus"| Gossip & CRDT & OT

    style Consensus fill:#fbbf24,stroke:#f59e0b,color:#000
    style Paxos fill:#a78bfa,stroke:#8b5cf6,color:#000
    style Raft fill:#a78bfa,stroke:#8b5cf6,color:#000
    style Gossip fill:#34d399,stroke:#10b981,color:#000
    style CRDT fill:#34d399,stroke:#10b981,color:#000

A module roadmap diagram. Lesson 21.1 (this lesson) defines the consensus problem. Lessons 21.2 and 21.3 present the two major solutions: Paxos (the classical, theoretical algorithm) and Raft (the understandable, practical alternative). Lessons 21.4 and 21.5 cover practical applications built on consensus: leader election and distributed locks. Lessons 21.6, 21.7, and 21.8 cover alternatives to strong consensus - gossip protocols for eventual propagation, CRDTs for mathematical convergence without coordination, and operational transformation for collaborative editing. The first branch (Paxos/Raft → leader election/locks) is strong consensus - all nodes agree on the exact same value. The second branch (gossip/CRDTs/OT) is weaker forms of agreement - eventual convergence or coordination-free operation. Both branches are essential: strong consensus for critical decisions (who is the leader?), weaker agreement for scalable data propagation (replicate a counter across 1,000 nodes without coordinating every increment).

Six Takeaways from This Lesson

1. Consensus = getting distributed nodes to agree on a single value despite crashes, lost messages, and no global clock. The three properties: agreement, validity, termination.

2. FLP Impossibility: in a purely asynchronous system, no deterministic consensus algorithm can guarantee termination. Practical algorithms (Paxos, Raft) use partial synchrony (timeouts) to achieve liveness while maintaining safety always.

3. Safety vs liveness: consensus algorithms guarantee safety always (never decide two different values) and liveness eventually (will decide once the network stabilizes). Stalling is acceptable; inconsistency is not.

4. 2PC solves distributed transactions but the coordinator is a single point of failure - if it crashes, participants block indefinitely. Paxos/Raft solve this by replicating the coordinator.

5. Strong consensus (Paxos, Raft) is expensive: message exchange for every decision. Eventual convergence (CRDTs, gossip) is cheaper but weaker. Choose based on correctness requirements.

6. Every major distributed database uses consensus internally: etcd (Raft), ZooKeeper (ZAB), CockroachDB (Raft), Spanner (Paxos), Kafka KRaft (Raft). Understanding consensus means understanding how these systems work.

What's Next

Lesson 21.2 covers Paxos - the classical consensus algorithm invented by Leslie Lamport in 1989. Nikhil walks through the algorithm, the intuition behind it, and why it's notoriously hard to understand.

Back to System Design Fundamentals