Consensus and Raft: Leader Election, Log Replication and the FLP Result

Version note: The code in this post was built and run with C# 14 and .NET 10.

Guess First

A five-node cluster is going to elect a leader. The rule is simple: if a node hears nothing from a leader for 150 milliseconds, it declares itself a candidate, votes for itself and asks the others for votes. Each node votes only once per term. The one that gets three of the five votes becomes leader.

To keep things "deterministic and easy to test", the team fixes every node's timeout at exactly 150 milliseconds, and the network delay is the same for every message. When the cluster starts, who becomes leader? How long does it take?

The Consensus Problem

We have run into the same question several times in earlier posts: when the leader crashes, who picks the new one, and what keeps two nodes from both believing they are leader (fifth post)? During a partition, which side is the majority (seventh post)? The common name for these questions is consensus: several nodes, some of which may crash, agreeing on a single value.

The classic definition requires three properties. Agreement: no two nodes decide different values. Validity: the decided value is one that some node proposed. Termination: every node that does not crash eventually decides. The first two are safety properties, the last a liveness property.

In practice consensus is about more than a single value: it is about a log. Total order broadcast, which we saw in the fifth post, delivers all messages to all nodes in the same order; making it fault-tolerant is equivalent to running consensus for each position in the log. If every node applies the same commands in that order, they all reach the same state (state machine replication). Lock services, leader election, cluster configuration and consistent replication are all built on this one mechanism.

FLP: Impossibility in an Asynchronous Network

In "Impossibility of Distributed Consensus with One Faulty Process", published in 1985, Fischer, Lynch and Paterson proved the most famous result in distributed systems. In an asynchronous system model (no upper bound on message delay or process speed, as in the second post), even if only one process may crash, there is no deterministic consensus algorithm that always terminates. The intuition is the same as the failure detector problem in the second post: if a slow node cannot be told apart from a crashed one, the algorithm either keeps waiting for that node (and may wait forever) or decides without waiting (and, if the node is alive, it may have reached a different decision).

The FLP (Fischer, Lynch, Paterson) result does not say consensus is impossible; it says safety and liveness cannot both be guaranteed in the asynchronous model. Practical algorithms get around it in three ways. They preserve safety under all conditions and leave liveness to periods when the network is partially synchronous. They use timeouts as failure detectors, but a false alarm does not break safety, it only slows progress. And they use randomness, which is exactly what the opening question is about.

A Brief Look at Paxos

Leslie Lamport's Paxos is considered the first practical solution to consensus in the crash-recovery model; the paper was written in 1989 but only published in 1998 as "The Part-Time Parliament", and Lamport followed it with a plain account, "Paxos Made Simple", in 2001. Paxos reaches agreement on a single value in two phases: a proposer first obtains promises from a majority for a ballot number (prepare/promise), then proposes a value with that number (accept). For a log you run Paxos for every position (Multi-Paxos) and optimize it with a stable leader; the paper leaves this part underspecified, so real implementations diverged considerably. Google's Chubby lock service uses Paxos.

That is exactly why Diego Ongaro and John Ousterhout proposed Raft in "In Search of an Understandable Consensus Algorithm", published at USENIX's (Advanced Computing Systems Association) ATC (Annual Technical Conference) in 2014: an algorithm with the same guarantees that splits the problem into leader election, log replication and safety, with understandability as an explicit design goal. They even measured it with a user study in the paper.

Raft: Terms and Leader Election

In Raft every node is in one of three roles: follower, candidate or leader. Time is divided into terms; each term begins with an election and has at most one leader. The term number works like a logical clock: as soon as a node sees a higher term than its own, it updates its term and returns to follower; it rejects messages with a lower term.

If a follower receives no heartbeat from the leader for a certain time (the election timeout), it increments its term, becomes a candidate, votes for itself and sends RequestVote to the other nodes. Each node votes only once per term and writes that vote (and the current term) to disk before answering; as we saw in the second post, a restarted node that votes a second time in the same term can cause two leaders to be elected. The candidate that gets a majority of votes becomes leader and immediately starts sending heartbeats. There is also an election restriction: a node does not vote for a candidate whose log is behind its own. This rule guarantees that every committed entry is present in the new leader's log.

Let us answer the opening question with a discrete-event simulation. Instead of real time we use an event queue; every event runs at a simulated millisecond, so the result is the same on every run. No log and no disk, just the election:

namespace Bookstore.Raft;

public enum Role { Follower, Candidate, Leader }

public abstract record Msg(int From, int Term);
public sealed record RequestVote(int From, int Term) : Msg(From, Term);
public sealed record Vote(int From, int Term, bool Granted) : Msg(From, Term);
public sealed record Heartbeat(int From, int Term) : Msg(From, Term);

public sealed class RaftNode(int id)
{
    public int Id { get; } = id;
    public Role Role { get; set; } = Role.Follower;
    public int Term { get; set; }
    public int? VotedFor { get; set; }
    public int Votes { get; set; }
    public bool Crashed { get; set; }
    public long TimerVersion { get; set; } // invalidates old election timers
}

// Discrete-event simulation of Raft leader election (no log, no disk)
public sealed class Simulation(int nodes, Func<Random, int> electionTimeout, int seed)
{
    private const int HeartbeatMs = 50, DelayMs = 5;
    private readonly PriorityQueue<Action, (int Time, long Seq)> _events = new();
    private readonly Random _random = new(seed);
    private long _seq;
    private int _now;

    public List<RaftNode> Nodes { get; } = [.. Enumerable.Range(1, nodes).Select(i => new RaftNode(i))];
    public bool Verbose { get; init; } = true;

    private void At(int time, Action action) => _events.Enqueue(action, (time, _seq++));
    private void Log(string text) { if (Verbose) Console.WriteLine($"{_now,5} ms  {text}"); }

    private void ResetTimer(RaftNode node)
    {
        long version = ++node.TimerVersion;
        At(_now + electionTimeout(_random), () =>
        {
            if (!node.Crashed && node.Role != Role.Leader && node.TimerVersion == version) StartElection(node);
        });
    }

    private void Send(RaftNode from, Msg msg, RaftNode to) =>
        At(_now + DelayMs, () => { if (!to.Crashed && !from.Crashed) Receive(to, msg); });

    private void Broadcast(RaftNode from, Msg msg) =>
        Nodes.Where(n => n != from).ToList().ForEach(n => Send(from, msg, n));

    private void StartElection(RaftNode node)
    {
        node.Role = Role.Candidate;
        node.Term++;
        node.VotedFor = node.Id;
        node.Votes = 1;
        Log($"n{node.Id} times out, becomes candidate for term {node.Term}");
        ResetTimer(node);
        Broadcast(node, new RequestVote(node.Id, node.Term));
    }

    private void Receive(RaftNode node, Msg msg)
    {
        if (msg.Term > node.Term) // a newer term always wins
        {
            node.Term = msg.Term;
            node.Role = Role.Follower;
            node.VotedFor = null;
        }
        RaftNode sender = Nodes[msg.From - 1];
        switch (msg)
        {
            case RequestVote rv:
                bool grant = rv.Term == node.Term && (node.VotedFor is null || node.VotedFor == rv.From);
                if (grant)
                {
                    node.VotedFor = rv.From;
                    ResetTimer(node);
                }
                Send(node, new Vote(node.Id, node.Term, grant), sender);
                break;
            case Vote { Granted: true } v when node.Role == Role.Candidate && v.Term == node.Term:
                if (++node.Votes == Nodes.Count / 2 + 1) BecomeLeader(node);
                break;
            case Heartbeat hb when hb.Term >= node.Term:
                node.Role = Role.Follower;
                ResetTimer(node);
                break;
        }
    }

    private void BecomeLeader(RaftNode node)
    {
        node.Role = Role.Leader;
        Log($"n{node.Id} wins term {node.Term} with {node.Votes}/{Nodes.Count} votes");
        void Beat()
        {
            if (node.Crashed || node.Role != Role.Leader) return;
            Broadcast(node, new Heartbeat(node.Id, node.Term));
            At(_now + HeartbeatMs, Beat);
        }
        Beat();
    }

    public void CrashLeaderAt(int time) => At(time, () =>
    {
        RaftNode? leader = Nodes.FirstOrDefault(n => n.Role == Role.Leader && !n.Crashed);
        if (leader is null) return;
        leader.Crashed = true;
        Log($"n{leader.Id} (leader of term {leader.Term}) crashes");
    });

    public RaftNode? Run(int until)
    {
        Nodes.ForEach(ResetTimer);
        while (_events.TryDequeue(out Action? action, out (int Time, long Seq) key) && key.Time <= until)
        {
            _now = key.Time;
            action();
        }
        return Nodes.SingleOrDefault(n => n is { Role: Role.Leader, Crashed: false });
    }
}

Two scenarios: randomized timeouts between 150 and 300 milliseconds, the example range in the paper, with the leader crashing at millisecond 1000; then a fixed 150 milliseconds for every node:

using Bookstore.Raft;

Console.WriteLine("--- randomized timeouts 150-300 ms, leader crashes at 1000 ms ---");
Simulation raft = new(5, r => r.Next(150, 301), seed: 3);
raft.CrashLeaderAt(1000);
RaftNode? leader = raft.Run(until: 2000);
Console.WriteLine($"leader at 2000 ms: n{leader?.Id}, term {leader?.Term}");

Console.WriteLine("--- fixed timeout 150 ms for every node ---");
Simulation fixedTimeouts = new(5, _ => 150, seed: 3) { Verbose = false };
RaftNode? none = fixedTimeouts.Run(until: 2000);
Console.WriteLine($"leader at 2000 ms: {(none is null ? "none" : $"n{none.Id}")}, " +
                  $"terms reached: {string.Join(",", fixedTimeouts.Nodes.Select(n => n.Term))}");

--- randomized timeouts 150-300 ms, leader crashes at 1000 ms ---
  179 ms  n4 times out, becomes candidate for term 1
  189 ms  n4 wins term 1 with 3/5 votes
 1000 ms  n4 (leader of term 1) crashes
 1244 ms  n1 times out, becomes candidate for term 2
 1244 ms  n2 times out, becomes candidate for term 2
 1254 ms  n1 wins term 2 with 3/5 votes
leader at 2000 ms: n1, term 2
--- fixed timeout 150 ms for every node ---
leader at 2000 ms: none, terms reached: 13,13,13,13,13

With randomized timeouts the first election was over at millisecond 189. After the leader crashed, n1 and n2 became candidates in the same millisecond; n1 collected three votes first and won, and n2 returned to follower when it received a heartbeat from the leader of the same term. The new leader was ready 254 milliseconds after the crash. With the fixed timeout, all five nodes become candidates at the same moment every time, everyone votes for themselves, nobody gets a majority, and although the term climbs to 13 in 2 seconds, no leader is ever elected. Safety was not broken (there are never two leaders), but there is no liveness. The opening request to "keep it deterministic" amounts to hand-building the endless loop FLP describes. Raft's randomized timeouts break that loop by keeping the chance of simultaneous candidacies low.

Log Replication and the Commit Index

The leader appends commands from clients to its log and sends them to followers in AppendEntries messages. Every AppendEntries also carries the index and term of the entry immediately preceding the new ones. If the follower does not have an entry with that term at that position in its log, it rejects the message, and the leader steps back one position and tries again. This consistency check provides the Log Matching property: if two logs contain an entry with the same index and term, the logs are identical up to that point.

An entry is committed once the leader has had it written to a majority of nodes. In the figure above, index 3 is on three of the five nodes; the leader advances its commit index to 3, applies the entry to its own state machine and answers the client. Index 4 is on only two nodes; if the leader crashes it may be lost, and since the client has not yet been told "done", that is not a problem. There is a subtle rule here: the leader commits by counting replicas only for entries from its own term; entries left over from earlier terms count as committed indirectly once an entry from its own term commits. Figure 8 in the paper shows step by step how, without this rule, even an entry written to a majority could be overwritten.

Reads have a trap too. If the leader answers from its own state, a new leader may have been elected without its knowledge, and it returns a stale value. That is why the Raft paper requires the leader, for linearizable reads, to confirm it is still leader by exchanging a round of heartbeats with a majority before answering. etcd's ReadIndex mechanism does this; some systems use lease-based reads that rely on clock bounds instead, which carries the risks that are the subject of the tenth post.

Where We Use Consensus, and Why We Do Not Write It Ourselves

The entire state of a Kubernetes cluster lives in etcd, and etcd is replicated with Raft. HashiCorp Consul uses Raft. Apache ZooKeeper uses Zab, a protocol similar to Raft. Kafka moved its ZooKeeper dependency to the Raft-based KRaft through KIP (Kafka Improvement Proposal) 500 and dropped ZooKeeper support entirely with version 4.0. Distributed databases such as CockroachDB and TiKV run a separate Raft group for every range of data.

As a .NET developer you almost never write this algorithm; you use it. If you need leader election, there is Kubernetes' Lease object or etcd's election API (Application Programming Interface); if you need a consistent counter or lock, a transaction in a database that already runs on Raft or Paxos is usually enough. The simulation above is for understanding why Raft is designed the way it is; it is not an implementation for production. A real Raft implementation needs snapshots, log compaction, membership changes, handling of disk errors and years of Jepsen-style testing. In the RaftScope visualization at raft.github.io you can stop a node and bring it back in another term to play through this post's scenarios in your browser.

Common Pitfalls

Running an even number of nodes. In a four-node cluster the majority is three and it tolerates the loss of only one node; a three-node cluster also tolerates one. The fourth node only adds cost. 2f + 1 nodes tolerate f crashes.

Not choosing the election timeout from network latency. The Raft paper recommends a timeout an order of magnitude larger than the broadcast time and a few orders of magnitude smaller than the mean time between failures. In a cross-region cluster a 150-millisecond timeout means constant elections.

Assuming reads from the leader are automatically linearizable. As you saw above, an answer given without confirming leadership may be stale.

Putting consensus in front of everything. A majority acknowledgement on every write pays the latency cost of the E branch of PACELC (if Partition: Availability or Consistency, Else: Latency or Consistency) from the seventh post. Use consensus for things that really need a single order (configuration, locks, the leader, sequence numbers).

Writing your own consensus algorithm. It is like writing your own encryption algorithm: it seems to work, but the bugs only show up in rare combinations of failures.

A Small Experiment

★☆☆ Change the number of nodes in the simulation from 5 to 3 and to 7. How long does it take to elect a new leader after the crash? Try a few runs with different seeds.

★★☆ Change the timeout range from 150–300 to 150–160 milliseconds. How does the number of split votes (elections in which nobody gets a majority) change? Measure it by adding a counter to StartElection.

★★★ Add a partition to the simulation: the leader and one follower on one side, the other three nodes on the other. What does the old leader do, and what does the other side do? When the partition heals, what happens to the old leader's term and role? Had the old leader accepted a client write during the partition, what would have happened to it?

Consensus lets a group of nodes agree on a single order. But what about several independent systems (two separate databases, or a database and a message broker) committing the same transaction together? That is the topic of the next post: atomic commit, two-phase commit (2PC), why everything stays locked when the coordinator crashes, and why it is avoided in microservices.