Hello everyone, welcome to the twenty-eighth issue of The Main Thread - a newsletter where we dissect distributed systems and AI engineering from first principles.
In today’s issue, we are going to talk about the backbone of distributed systems - consensus algorithms, especially Raft.
Getting multiple computers to agree on something is fundamentally impossible.
Not difficult or expensive - mathematically impossible under certain conditions. The Fischer-Lynch-Paterson (FLP) impossibility result from 1985 proved that no deterministic consensus algorithm can guarantee termination in an async system where even one process might fail.
And yet, our distributed systems reach consensus constantly. CockroachDB commits transactions across datacenters, Consul agrees on service health, etcd coordinates our k8s cluster. How?
The answer lies in understanding exactly which impossible condition we sidestep, and how. Raft, designed by Diego Ongaro and John Ousterhout in 2014, doesn’t defeat the impossible result but it navigates around it with carefully chosen tradeoffs. By the end of this article, we will understand those tradeoffs deeply enough to debug consensus failures.
What Are We Actually Solving?
Before diving into the mechanics of Raft, let’s be precise about the problem.
Consensus means getting multiple nodes to agree on a single value such that:
Agreement: All non-faulty nodes decide on the same value.
Validity: The decided value was proposed by some node.
Termination: All non-faulty nodes eventually decide.
This sounds simple, but it’s not. Here’s why:
Imagine three nodes trying to agree on who’s the leader. Node A proposes itself. Node B proposes itself. Due to network delay, it is possible that A sees B’s proposal before C does, but C sees B’s proposal before A’s proposal. Without careful coordination, we get split-brain: some node think A is leader, other think B is.
The FLP result says that in pure async system (no timing assumptions), with even one faulty process, there is always some execution where the algorithm never terminates. The system can run forever deciding.
How Raft Escapes FLP
It doesn’t assume pure asynchrony by using timeouts. If a follower doesn’t hear from the leader within an election timeout, it assumes the leader is dead and starts and election. This timing assumption that the network is eventually synchronous enough for messages to arrive within a bounded time, is what makes progress possible.
However, the tradeoff is that if the timeout is wrong (network slower than expected), we get unnecessary elections. If the network is truly asynchronous forever, Raft might never elect a stable leader. In practice, networks are “mostly synchronous“ and Raft works.
Raft’s Core Abstraction: Replicated Log
Raft’s fundamental insight is reducing consensus to a simpler problem: maintaining a replicated log.
Instead of agreeing on arbitrary values, nodes agree on a sequence of log entries. Each entry contains a command. If all nodes have the same log in same order, they can apply commands deterministically and reach the same state.
Node A log: [set x=1] [set y=2] [set x=3]
Node B log: [set x=1] [set y=2] [set x=3]
Node C log: [set x=1] [set y=2] [set x=3]
↓ ↓ ↓
All nodes: x=3, y=2With this, the consensus problem becomes: ensure all logs are identical.
Raft decomposes this into three subproblems:
Leader Election: Choose one node to coordinate
Log Replication: Leader accepts commands and replicates to followers
Safety: Ensure elected leaders have all committed entries.
Leader Election: Step by Step
Raft nodes exist in one of three states: follower, candidate, or leader.
