Prerequisites

The Consensus Problem

Consensus is the problem of getting a group of nodes to agree on a single value, despite some of them failing and the network delivering messages late, out of order, or not at all.

Why This Is Hard

The FLP impossibility result establishes that in an asynchronous network with even one faulty node, no algorithm can guarantee consensus will always terminate. Since a slow node is indistinguishable from a dead one, no bound on waiting is ever sufficient.

Quorum Intersection

Every correct consensus protocol rests on one structural fact: any two majorities of the same set must share at least one member. That shared member carries knowledge forward.

From Consensus to Replicated State Machines

Agreeing on one value is rarely the goal. The practical application is agreeing on an ordered sequence of commands, which every replica then applies identically.

Consensus is used repeatedly, once per log position. The replicated log becomes the single source of truth, and each replica is a deterministic function of that log.

Raft: Leader-Based Consensus

Raft was designed explicitly for understandability. It decomposes consensus into three separable problems and constrains the design so fewer states are possible.

Node States

Terms as Logical Time

Raft divides time into numbered terms, each beginning with an election. Terms act as a logical clock that lets nodes detect stale information immediately.

function handleIncomingMessage(node, message) {
    if (message.term > node.currentTerm) {
        node.currentTerm = message.term;
        node.votedFor = null;
        node.state = "follower";
        persistState(node);
    }

    if (message.term < node.currentTerm) {
        return {
            term: node.currentTerm,
            success: false,
            reason: "stale term"
        };
    }

    return processMessage(node, message);
}

Leader Election

A follower that hears nothing from a leader within its election timeout assumes the leader has failed, increments the term, and campaigns.

async function startElection(node) {
    node.currentTerm += 1;
    node.state = "candidate";
    node.votedFor = node.id;
    persistState(node);

    let votes = 1;
    const required = Math.floor(node.peers.length / 2) + 1;

    const requests = node.peers.map(peer =>
        requestVote(peer, {
            term:         node.currentTerm,
            candidateId:  node.id,
            lastLogIndex: node.log.length - 1,
            lastLogTerm:  node.log.at(-1)?.term ?? 0
        })
    );

    for (const response of await Promise.allSettled(requests)) {
        if (response.status !== "fulfilled") continue;

        if (response.value.term > node.currentTerm) {
            node.currentTerm = response.value.term;
            node.state = "follower";
            node.votedFor = null;
            persistState(node);
            return { elected: false, reason: "higher term observed" };
        }

        if (response.value.voteGranted) votes += 1;
    }

    if (votes >= required) {
        node.state = "leader";
        initializeLeaderState(node);
        return { elected: true, term: node.currentTerm, votes };
    }

    node.state = "follower";
    return { elected: false, reason: "insufficient votes", votes };
}

Voting Restrictions

Randomized Timeouts

If every follower timed out simultaneously, all would campaign, split the vote, and repeat indefinitely. Randomization makes one node consistently reach the timeout first.

function nextElectionTimeout(config) {
    const spread = config.maxTimeoutMs - config.minTimeoutMs;
    return config.minTimeoutMs + Math.floor(Math.random() * spread);
}

Log Replication

Once elected, the leader is the sole entry point for commands. It appends locally, replicates to followers, and commits once a majority has stored the entry.

async function proposeCommand(leader, command) {
    const entry = {
        term:  leader.currentTerm,
        index: leader.log.length,
        command
    };

    leader.log.push(entry);
    await persistLog(leader);

    const required = Math.floor(leader.peers.length / 2) + 1;
    let stored = 1;

    await Promise.allSettled(
        leader.peers.map(async peer => {
            const ok = await replicateToFollower(leader, peer);
            if (ok) stored += 1;
        })
    );

    if (stored < required) {
        return { committed: false, reason: "quorum not reached" };
    }

    if (entry.term !== leader.currentTerm) {
        return { committed: false, reason: "term changed during replication" };
    }

    leader.commitIndex = entry.index;
    const result = await applyToStateMachine(leader, entry.command);

    return { committed: true, index: entry.index, result };
}

The Log Matching Property

Each replication message includes the index and term of the preceding entry. A follower rejects the append if it does not match, and the leader steps backwards until it finds the point of agreement.

Paxos

Paxos preceded Raft and solves the same problem. It is more general, which is both its strength and the reason it is harder to implement correctly.

The Two Phases

Multi-Paxos and the Convergence with Raft

Running full Paxos per decision costs two round trips. Multi-Paxos elects a stable proposer that skips the prepare phase while it remains uncontested, reducing steady-state cost to one round trip.

Reads Require Care

Writes go through consensus and are safe. Reads are where otherwise-correct systems introduce linearizability violations, because a stale leader does not know it has been deposed.

async function linearizableRead(leader, key) {
    if (leader.state !== "leader") {
        return { ok: false, redirect: leader.knownLeaderId };
    }

    const readIndex = leader.commitIndex;
    const confirmed = await confirmLeadershipViaHeartbeat(leader);

    if (!confirmed) {
        return { ok: false, reason: "leadership not confirmed" };
    }

    await waitForApplied(leader, readIndex);

    return { ok: true, value: leader.stateMachine.get(key) };
}

Membership Changes

Adding or removing nodes changes what constitutes a majority. Switching directly creates a window where two disjoint majorities can exist under different configurations.

Log Compaction

The log grows without bound. Snapshots capture the state machine at a point so earlier entries can be discarded.

{
    "snapshotIndex": 184203,
    "snapshotTerm": 47,
    "configuration": ["node-1", "node-2", "node-3", "node-4", "node-5"],
    "stateHash": "sha256:9f2b71c4...",
    "createdAt": "2026-09-24T05:58:11Z",
    "sizeBytes": 47185920
}

What Consensus Costs

What Belongs in Consensus

Build Versus Adopt

Monitoring

Common Design Mistakes

System Design Interview Discussion

Design Checklist

Knowledge Check

Summary

Consensus is agreement among nodes despite failures and unreliable networks. FLP impossibility shows termination cannot be guaranteed, so practical protocols preserve safety absolutely and treat progress as best-effort.

Every correct protocol rests on quorum intersection. Because two majorities of the same cluster must share a member, knowledge of any committed decision carries forward, and two disjoint groups can never both proceed.

Raft applies this through a leader-based design with numbered terms. Elections require a majority and restrict voting to candidates whose logs are sufficiently current, which guarantees committed entries survive leadership change. Log replication commits once a majority has durably stored an entry.

Paxos solves the same problem more generally through prepare and accept phases, with Multi-Paxos converging on a design close to Raft. The practical difference is specification: Raft defines leadership, log structure, and membership change explicitly, which is why implementations resemble each other and the paper.