Consensus Algorithms (Raft & Paxos)

How do distributed systems agree on a single truth when machines crash, networks partition, and messages get lost? Consensus is the hardest problem in distributed computing.

Why Consensus Matters

Every distributed database, every replicated state machine, and every leader election mechanism needs consensus:

The Problem Statement

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph Problem["The Consensus Problem"]
        C(("Client")) -->|"write X=5"| N1["Node 1"]
        C -->|"write X=7"| N2["Node 2"]
        N1 & N2 & N3["Node 3"] -->|"???"| Q{"What is X?<br/>All must agree!"}
    end

    style Q fill:#FFCDD2,stroke:#C62828,color:#000

Requirements for valid consensus:

Raft — Consensus Made Understandable

Raft was designed in 2014 explicitly to be easier to understand than Paxos while providing the same guarantees.

Three Roles

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
stateDiagram-v2
    [*] --> Follower: Starts as follower
    Follower --> Candidate: Election timeout<br/>(no heartbeat received)
    Candidate --> Leader: Wins election<br/>(majority votes)
    Candidate --> Follower: Loses election<br/>(higher term seen)
    Leader --> Follower: Higher term discovered

Leader Election

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
sequenceDiagram
    participant F1 as Node A (Follower)
    participant F2 as Node B (Follower)
    participant F3 as Node C (Follower)

    Note over F1,F3: Leader crashed. Election timeout fires on Node A first.
    F1->>F1: Increment term (term=2), become Candidate
    F1->>F2: RequestVote(term=2, lastLogIndex=5)
    F1->>F3: RequestVote(term=2, lastLogIndex=5)
    F2->>F1: VoteGranted (term=2)
    F3->>F1: VoteGranted (term=2)
    Note over F1: 3/3 votes = majority ✅
    F1->>F1: Become Leader (term=2)
    F1->>F2: AppendEntries (heartbeat)
    F1->>F3: AppendEntries (heartbeat)

Election rules: 1. Follower's election timeout fires (randomized 150-300ms) 2. Becomes Candidate, increments term, votes for self 3. Sends RequestVote to all other nodes 4. Wins if receives majority votes (>N/2) 5. Each node votes at most ONCE per term 6. Candidate with stale log (lower lastLogIndex) gets rejected

Log Replication

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2

    C->>L: Write X=5
    L->>L: Append to local log (uncommitted)
    L->>F1: AppendEntries(entry: X=5)
    L->>F2: AppendEntries(entry: X=5)
    F1->>L: ACK (replicated)
    F2->>L: ACK (replicated)
    Note over L: Majority ACKed (2/3) → COMMIT
    L->>L: Apply to state machine
    L->>C: Success (X=5 committed)
    L->>F1: Next heartbeat (commitIndex updated)
    L->>F2: Next heartbeat (commitIndex updated)
    Note over F1,F2: Apply committed entries to local state machine

Commit rule: A log entry is committed when replicated to a majority of nodes. Even if the leader crashes after commit, the entry is safe (a new leader will have it).

Safety Guarantee

If a log entry is committed in a given term, that entry will be present 
in the logs of ALL leaders for all higher-numbered terms.

This ensures: once you tell the client "write succeeded," that write survives any future leader changes.

Paxos — The Original (Theoretical)

Paxos (1989, Lamport) is mathematically proven correct but notoriously difficult to implement.

Roles in Paxos

Basic Paxos (Single Value)

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3

    Note over P,A3: Phase 1: PREPARE
    P->>A1: Prepare(n=1)
    P->>A2: Prepare(n=1)
    P->>A3: Prepare(n=1)
    A1->>P: Promise(n=1, no prior value)
    A2->>P: Promise(n=1, no prior value)
    A3->>P: Promise(n=1, no prior value)

    Note over P,A3: Phase 2: ACCEPT
    P->>A1: Accept(n=1, value="X=5")
    P->>A2: Accept(n=1, value="X=5")
    P->>A3: Accept(n=1, value="X=5")
    A1->>P: Accepted(n=1)
    A2->>P: Accepted(n=1)
    Note over P: Majority accepted → VALUE CHOSEN

Phase 1 (Prepare): - Proposer picks a unique proposal number n - Sends Prepare(n) to all acceptors - Acceptors promise not to accept proposals with number < n

Phase 2 (Accept): - If majority promised, proposer sends Accept(n, value) - Acceptors accept if they haven't promised a higher number - If majority accepts, value is chosen

Raft vs Paxos

Practical Considerations

Quorum Size

For N nodes: quorum = ⌊N/2⌋ + 1 (majority)

3 nodes → quorum 2 → tolerates 1 failure
5 nodes → quorum 3 → tolerates 2 failures  
7 nodes → quorum 4 → tolerates 3 failures

Performance Implications

Network Partitions

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph Partition1["Partition A (majority)"]
        L["Leader"] & F1["Follower 1"]
    end
    subgraph Partition2["Partition B (minority)"]
        F2["Follower 2"]
    end

    Partition1 -.-|"network<br/>partition"| Partition2

    style Partition1 fill:#E8F5E9,stroke:#2E7D32,color:#000
    style Partition2 fill:#FFCDD2,stroke:#C62828,color:#000

• Partition A (leader + 1 follower = majority): continues serving reads AND writes
• Partition B (1 follower = minority): cannot elect a new leader, becomes read-only (stale)
• When partition heals: follower in B catches up from leader's log

Interview Questions