Consensus and Raft: One Truth at the Price of a Quorum

By Sergey Nosov

16 October 2026

Suppose a sign-up service keeps its accounts on two replicas, and a network partition cuts them apart. On each side, someone asks for the username kestrel, and each replica says yes. When the network heals, the replicas can merge their data, but no merge can repair the result. Two people were promised the same name, and one of them will lose it.

Many operations never face that problem. Counting likes, tracking who is online, and editing a shared document can all run on every replica and merge later. Others have no safe merge: claiming a unique username, spending from a balance that must not go negative, choosing the one node that leads, changing the cluster’s own membership. There the replicas must agree before anyone gets an answer. That is consensus: getting a cluster of unreliable machines to act as one reliable machine.

Consensus buys one truth at the price of a quorum. This article explains when that price is worth paying and how Raft, the algorithm inside etcd, Consul, and RabbitMQ’s quorum queues, pays it. It shows Raft’s rules in C#, tested on .NET 10, and what a three-node etcd 3.7.2 cluster does when it loses its leader and then its majority.

Merge or Agree

A CRDT, short for conflict-free replicated data type, lets every replica accept writes on its own. In the state-based form, its merge is commutative, associative, and idempotent. Replicas that have seen the same updates therefore reach the same state, whatever the order of arrival and however often an update was repeated. A grow-only counter, for example, keeps one count per replica, and a merge takes the larger value of each.

Whether merging is enough has a precise answer. In a 2014 paper, “Coordination Avoidance in Database Systems,” Peter Bailis and five coauthors named the deciding property invariant confluence. Informally, it holds when “divergent but I-valid database states can be merged into a valid database state.” An I-valid state satisfies the application’s invariants, the rules its data must always obey.

The paper proves the property necessary and sufficient. Where it holds for a set of operations and invariants, replicas can run them without coordination, stay available, and converge without breaking an invariant. Where it fails, no system can promise all of that. Invariant confluence draws the line where practitioners need it:

So ask of each operation: can two replicas each say yes on their own and still be right after they merge? If they can, merge, and keep answering during a partition, as my article on the CAP theorem describes. If they cannot, the replicas must agree first, because a merge that keeps both answers is precisely the bug.

Why Agreement Is Hard

First, you cannot tell slow from dead. A node that goes silent may have crashed, or its messages may be stuck in a congested network. Every failure detector guesses, usually with a timeout.

Second, a wrong guess invites split brain. If each half of a partitioned cluster decides that the other half is dead and acts on that guess alone, both halves may elect a leader and accept writes. Two truths then diverge, and two truths are worse than none.

Third, a proof shows what the first fact costs. In 1985, Michael Fischer, Nancy Lynch, and Michael Paterson published what they called “the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death.” Their model bounds neither process speeds nor message delays and has no synchronized clocks, “so algorithms based on time-outs, for example, cannot be used.” No process can tell whether another “has died (stopped entirely) or is just running very slowly.” One crash at the wrong moment can then keep any deterministic protocol in that model from ever deciding.

The result, known as FLP after its authors, does not make consensus impossible in practice, and the authors said so. They called for models with more realistic assumptions about timing. Practical algorithms rely on such assumptions, but only for progress. The Raft paper requires that “safety must not depend on timing.” Whatever the delays, losses, duplication, or reordering of messages, Raft never returns an incorrect result, provided that nodes fail only by stopping and keep what they stored. Timing decides only when the cluster moves forward: it needs messages to arrive well within its election timeout.

Raft does not tolerate nodes that lie. Such faults are called Byzantine, after a 1982 paper by Leslie Lamport, Robert Shostak, and Marshall Pease, and tolerating them costs more. Miguel Castro and Barbara Liskov wrote in 1999 that where messages may be delayed, lost, or reordered, “3f+1 is the minimum number of replicas” that can survive f faulty ones. Raft survives f crashes with 2f + 1 nodes. When nodes merely crash instead of lie, agreement gets a full node cheaper per failure.

Raft in Three Ideas

Before Raft, the standard answer was Leslie Lamport’s Paxos, which Diego Ongaro and John Ousterhout of Stanford University called “exceptionally difficult to understand.” Their 2014 paper, “In Search of an Understandable Consensus Algorithm,” introduced Raft with understandability as its primary goal. It was important, they wrote, “not just for the algorithm to work, but for it to be obvious why it works.”

Raft keeps a replicated log. Every node runs the same deterministic state machine, such as a key-value store, and applies the commands in its log in order. If every log holds the same commands in the same order, every node reaches the same state. Raft’s job is to keep the logs consistent, and it does that with three ideas.

Idea 1: Elect One Leader

Every node is a follower, a candidate, or the leader. Time is divided into numbered terms, which act as a logical clock. Every message carries its sender’s term. A node that sees a higher term adopts it, and a node that receives a message from an older term rejects it. Each term begins with an election.

The leader sends heartbeats. A follower that hears nothing for its election timeout assumes the leader is gone: it increments its term, votes for itself, and asks the others for their votes. Each node grants at most one vote per term, first come, first served, and a candidate that collects votes from a majority leads for that term. Each node records its vote on disk before it answers. Any two majorities of the same membership share a node, so two candidates cannot both win the same term.

Each node draws its election timeout at random from a range; the paper’s example is 150 to 300 milliseconds. Usually one node times out first and wins before the others time out. When two become candidates at once and split the vote, the term ends without a leader, and fresh random timeouts break the tie.

One leader per term makes the leader the cluster’s single point of order without making it a single point of failure: losing it only triggers the next election. The rule promises at most one leader per term, not at most one node that believes it is the leader. A leader that has been cut off can keep believing for a while, and the experiment below caught exactly that.

Idea 2: Replicate a Log

Clients send commands to the leader. The leader appends each command to its own log and sends it to the followers in an AppendEntries message. A heartbeat is simply an AppendEntries message with no entries, so the data plane and the failure detector are one mechanism.

Each AppendEntries also names the index and term of the entry just before the new ones. A follower accepts the batch only if its own log has an entry at that index with that term. Otherwise it refuses, and the leader retries from an earlier entry until the two logs match.

From there, the follower deletes any entry that conflicts with a new one, along with all that follow it, and appends the new entries it lacks. As a result, two logs that hold an entry with the same index and term are identical up to that entry: the Log Matching Property.

The paper calls an entry committed, and safe to apply, once “the leader that created the entry has replicated it on a majority of the servers.” The overlap that keeps two leaders out of one term also protects that entry: every later majority contains a node that holds it. The truth cannot fork.

Idea 3: Three Safety Rules

All three ideas lean on the majority. It elects the leader, commits each entry, and carries every committed entry into the next term. The majority is the unit of truth. Lose it, and a well-built system refuses to guess.

The Rules in C#

The sample below is the receiving side of Raft’s two messages. It follows Figure 2 of the paper, which specifies the messages, the state, and the rules on one page. It leaves out timers, roles, the leader’s side, snapshots, and membership changes. It also keeps its state in memory, while Figure 2 requires a node to save the term, the vote, and the log to stable storage before it responds.

public record LogEntry(
    long Term, string Command);

public record AppendEntries(
    long Term,
    string LeaderId,
    long PrevLogIndex,
    long PrevLogTerm,
    LogEntry[] Entries,
    long LeaderCommit);

public record RequestVote(
    long Term,
    string CandidateId,
    long LastLogIndex,
    long LastLogTerm);

public record Reply(
    long Term, bool Success);

Term is the leader’s term, and LeaderId lets a follower redirect clients. PrevLogIndex and PrevLogTerm say where the batch attaches. An empty Entries array is a heartbeat, and LeaderCommit reports how far the leader has committed. RequestVote carries the candidate’s last index and term for the election restriction. One Reply serves both messages: it returns the receiver’s term, so a stale sender learns it is stale, and whether the request succeeded.

public sealed class Node
{
    // A real node persists these
    // three before it replies.
    long currentTerm;
    string? votedFor;
    readonly List<LogEntry> log = [];

    long commitIndex;

    public long CommitIndex => commitIndex;
    public IReadOnlyList<LogEntry> Log => log;

    long LastIndex => log.Count;
    long LastTerm =>
        log.Count == 0 ? 0 : log[^1].Term;

    // Raft numbers entries from 1.
    long TermAt(long i) =>
        i == 0 ? 0 : log[(int)i - 1].Term;

    // Drop entry i and the rest.
    void TruncateFrom(long i) =>
        log.RemoveRange((int)i - 1, log.Count - (int)i + 1);

    Reply Refuse() => new(currentTerm, false);
    Reply Accept() => new(currentTerm, true);

    void ObserveTerm(long term)
    {
        if (term > currentTerm)
        {
            currentTerm = term;
            votedFor = null;
        }
    }

    public Reply Handle(RequestVote req)
    {
        ObserveTerm(req.Term);
        if (req.Term < currentTerm)
            return Refuse();

        // Election restriction
        var upToDate = req.LastLogTerm > LastTerm
            || (req.LastLogTerm == LastTerm
                && req.LastLogIndex >= LastIndex);

        // One vote per term
        var free = votedFor is null
            || votedFor == req.CandidateId;

        if (!upToDate || !free)
            return Refuse();

        votedFor = req.CandidateId;
        return Accept();
    }

    public Reply Handle(AppendEntries req)
    {
        ObserveTerm(req.Term);
        // Refuse a stale leader
        if (req.Term < currentTerm)
            return Refuse();

        // The batch must attach to
        // a prefix this log holds
        if (req.PrevLogIndex > LastIndex
            || TermAt(req.PrevLogIndex) != req.PrevLogTerm)
            return Refuse();

        // Cut only on a conflict
        var index = req.PrevLogIndex;
        foreach (var entry in req.Entries)
        {
            index++;
            if (index <= LastIndex)
            {
                if (TermAt(index) == entry.Term)
                    continue;
                TruncateFrom(index);
            }
            log.Add(entry);
        }

        // Commit what this request
        // proved, never backward
        commitIndex = Math.Max(commitIndex,
            Math.Min(req.LeaderCommit, index));
        return Accept();
    }
}

Most lines map one to one onto Figure 2’s rules. Two hide traps, and the test harness behind the sample includes a shortcut version of each to show it failing:

Read literally, Figure 2’s commit rule can also move the commit index backward when a re-sent message proves less than the follower has already committed. The Math.Max call prevents that, the same guard that etcd’s raft library writes as “never decrease commit.” The harness runs twenty-four checks, covering both traps, that guard, stale leaders, one vote per term, and the election restriction.

Treat the sample as a way to read the rules, not as something to ship. Even etcd’s raft library implements only the algorithm: “both network and disk IO are left to the user.”

Watching Raft in etcd

Kubernetes documents etcd as its “backing store for all cluster data,” and etcd is a Raft cluster. The test cluster runs three etcd 3.7.2 nodes in containers on one virtual machine, with etcd’s default timing: a heartbeat every 100 milliseconds and an election timeout of 1,000 milliseconds. Each node draws its actual timeout at random between 1.0 and 1.9 seconds whenever it becomes a follower or a candidate.

Two Raft extensions are on. The server code enables CheckQuorum, under which a leader steps down when it cannot hear from a majority, and the --pre-vote flag defaults to true. The test cuts the leader off by disconnecting it from the container network. The leader keeps running, and a client on the same node can still reach it, but it cannot reach the other two nodes.

Across eight cuts, the node logs show a new leader at the next term about 0.9 to 1.5 seconds after the cut. A follower counts its timeout in 100-millisecond ticks from the last heartbeat, which arrived just before the cut. The election itself, from the first pre-vote request to the new leader, took 5 to 25 milliseconds.

Nearly all of the wait was the timeout, the price of not mistaking slow for dead. The Raft paper predicts it: after a leader crash, “the system will be unavailable for roughly the election timeout.” The logs show when the leader changed, not when clients could write again.

CheckQuorum demoted the old leader about 1.0 to 1.8 seconds after the cut, when it logged “stepped down to follower since quorum is not active.” In seven of the eight cuts, that came after the takeover, so for up to 0.8 seconds two nodes each believed they led, in different terms. The old one could commit nothing without a majority. Ongaro’s dissertation explains why the step-down exists: a cut-off leader that a client can still reach “could delay a request from that client forever.”

On the cut-off node, a write waited for etcdctl’s 5-second default timeout and failed, and so did an ordinary read. A serializable read answered at once. The transcript omits the warning line that the client printed before each error:

$ etcdctl put /demo/color red
Error: context deadline exceeded
$ etcdctl get /demo/color
Error: context deadline exceeded
$ etcdctl get /demo/color \
    --consistency=s
/demo/color
blue

Reads in etcd are linearizable by default, and its documentation explains the cost: “linearized requests must go through the Raft consensus process.” A serializable read skips that step, and the same page warns that it “may access stale data with respect to quorum.” Here it returned blue, the value from before the cut, although the majority side had already changed it to green.

When the node was reconnected, it rejoined as a follower of the new leader, caught up, and returned green to an ordinary read. Its term had not moved while it was cut off, although it had started a pre-vote at that term every 1.5 seconds.

That is Pre-Vote, as the dissertation describes it. A candidate increments its term only “if it first learns from a majority of the cluster that they would be willing to grant the candidate their votes.” Without Pre-Vote, a returning node would bring back a larger term, which “will force the cluster leader to step down.” Here the other two nodes rejected the returning node’s pre-vote requests, and the leader kept its term.

Last, the test killed both followers, leaving the leader alone. In two runs, it went on believing it was the leader for about 1.5 and 2.0 seconds after the second follower died, until CheckQuorum demoted it. Writes and ordinary reads timed out again, and a health check said why (wrapped):

$ etcdctl endpoint health
127.0.0.1:2379 is unhealthy:
failed to commit proposal:
context deadline exceeded
Error: unhealthy cluster

A serializable read still answered with the last value the node had. When the two nodes restarted, the cluster elected a leader for the next term within 1.5 seconds of the restart command, and writes succeeded again. The etcd FAQ describes both kinds of recovery. After a partition, etcd resumes automatically and safely once the network recovers. After a power loss, it replays its log from disk and rejoins the cluster.

The Kubernetes documentation names the consequence: while etcd has no leader, “a cluster cannot make any changes to its current state, which implies no new pods can be scheduled.” If a majority of members fail for good, it adds, “the scheduled pods might continue to run.” Workloads may keep running, but the control plane cannot change them.

Where Raft Runs

You consume Raft far more often than you implement it, and you probably run it already:

Not every consensus system runs Raft. ZooKeeper uses its own protocol, called Zab. Google’s Spanner and Amazon’s DynamoDB use Paxos. What follows applies to every operation that goes through consensus, whichever protocol runs it.

What Consensus Costs

What Consensus Leaves to You

A Checklist

The Raft, leader election, and quorum entries in my Software Development Principles series list warning signs, such as a missing pre-vote step that lets a rejoining node disrupt the leader. Before you depend on consensus, ask:

Consensus buys one truth at the price of a quorum. Spend it where a single truth is genuinely required, and know what every system you depend on does when its majority is gone. A well-built one refuses to guess.

Further Reading