Leader Election in Distributed Systems: Raft vs Paxos

The Future Today: From the president of OpenAI to the CEO of Google, we talk to the actual people changing the world with AI. And then we put all of their insights, advice, and business ingenuity into our newsletter. Join 75K Readers →

ChatGPT and Claude aren't just answering questions. Employees are connecting them directly to Notion, Linear, Jira, and the rest of your stack — with no security visibility into what data moves or what actions they take.

Harmonic Security gives your team the visibility to control it.

See what's connected

Global hiring doesn't come with a playbook. Join Oyster's webinars and events to learn how leading companies are hiring, expanding, and staying compliant across borders.

Explore Upcoming Events

Every Kubernetes cluster you've deployed runs a hidden election. Every 3 to 5 seconds, nodes inside etcd exchange heartbeats to confirm: "Yes, you're still the boss." The moment those heartbeats stop, an election kicks off in under 300 milliseconds. Your pods keep running because a consensus algorithm settled a leadership dispute before you noticed.

That algorithm is called Raft. Before Raft existed, the only real option was Paxos, an algorithm so hard to understand that its creator, Leslie Lamport, had to publish a follow up paper titled "Paxos Made Simple" because nobody could parse the original.

Why do distributed systems need a leader, what goes wrong without one, and how do Raft and Paxos actually work once you strip the academic jargon?

Imagine 5 database replicas accepting writes simultaneously. Client A writes balance = 500 to Node 1. Client B writes balance = 0 to Node 3. Same key, different values, no coordination. Which one wins?

Nobody knows. And that's the problem.

A leader (sometimes called a primary) is the single node that serializes all writes. Every write goes through the leader first, then gets replicated to followers in order. One authority, one sequence, no conflicts.

etcd does this for Kubernetes. ZooKeeper did it for Hadoop and Kafka. Google Chubby does it across Google's entire infrastructure.

But picking a leader creates a new problem: what happens when the leader dies?

When a network partition splits a cluster into two groups, both sides might think the leader is gone. Both sides elect their own leader. Now you have two leaders accepting writes independently.

This is called split brain, and it's one of the nastiest failure modes in distributed systems. Why? Because it doesn't crash. It doesn't throw errors. Both partitions happily accept writes while data silently diverges. You discover the damage weeks later when someone notices that Order #4821 shows "shipped" on one replica and "cancelled" on another.

The fix is brutal in its simplicity: quorum voting. You need a strict majority (more than half the nodes) to elect a leader. In a 5 node cluster, you need at least 3 votes. Since both sides of a partition can't both have a majority, only one side can elect a leader. The other side goes read only or stops entirely.

This is also why production clusters use odd numbers: 3, 5, or 7 nodes. A 4 node cluster can only tolerate 1 failure (needs 3 for quorum). A 5 node cluster can also tolerate 2 failures (needs 3 for quorum). Same fault tolerance, fewer machines.

Diego Ongaro and John Ousterhout published Raft in 2014 at Stanford. The paper's title says everything about their motivation: "In Search of an Understandable Consensus Algorithm."

They weren't trying to invent something new. They were trying to make Paxos understandable. And they succeeded. In a study of 43 students across two universities, 33 answered Raft questions better than Paxos questions after learning both.

Raft breaks consensus into three clean subproblems: leader election, log replication, and safety. Here's how the election works.

Every node starts in one of three states: Follower, Candidate, or Leader.

Followers are passive. They do nothing except listen for heartbeats from the current leader and respond to vote requests. If a follower doesn't hear from the leader within a randomized election timeout (typically 150 to 300 ms), it assumes the leader is dead.

That follower then promotes itself to Candidate. It increments a counter called the term (a logical clock that increases with every election), votes for itself, and broadcasts a "vote for me" request to every other node.

If the candidate gets votes from a majority, it becomes the Leader. The new leader immediately starts sending heartbeats to all followers, resetting their election timers. As long as heartbeats keep flowing, no new election happens.

The randomized timeout is what makes this work in practice. If every node had the same timeout, they'd all become candidates at the same time, split the vote, and nobody would win. Randomization means one node almost always times out first and wins cleanly.

One rule that separates Raft from Paxos: only a node with an up to date log can become leader. Raft bakes safety directly into the election. Paxos allows any node to become leader and then catch up afterward.

Leslie Lamport described Paxos in 1989 using a metaphor about legislators on a fictional Greek island. The metaphor was so confusing that the paper wasn't published until 1998, and even then, Lamport had to write "Paxos Made Simple" in 2001 because practitioners still couldn't implement it.

Paxos uses three roles: Proposers, Acceptors, and Learners. In practice, a single node often plays all three roles, but understanding them separately makes the protocol click.

The protocol runs in two phases.

Phase 1 (Prepare): A Proposer picks a proposal number and sends a "prepare" message to a majority of Acceptors. Each Acceptor promises not to accept any proposal with a lower number. If the Acceptor already accepted a previous value, it sends that value back.

Phase 2 (Accept): If the Proposer gets promises from a majority, it sends an "accept" message with the actual value. Acceptors accept it if they haven't made a newer promise in the meantime. Once a majority accepts, the value is chosen. Learners then discover the decided value.

Basic Paxos has no dedicated leader. Any node can be a Proposer at any time. Sounds flexible, but it creates a livelock problem: two Proposers can keep outbidding each other's proposal numbers forever, and nothing ever gets decided.

That's why production systems use Multi Paxos, which elects a stable leader Proposer so Phase 1 only runs once. After that, the leader can skip straight to Phase 2 for every subsequent value. Multi Paxos ends up looking a lot like Raft, which begs the obvious question: why bother with Paxos at all?

The throughput difference in normal operation is negligible. Both algorithms bottleneck on disk sync and network round trips, not on the consensus logic itself. The real difference is in how easy they are to implement correctly and debug when things go wrong.

Say you have a 5 node Raft cluster and the leader crashes.

The remaining 4 followers are still listening for heartbeats. Each has a randomized election timeout. Node 3 happens to timeout first (say, after 200ms). It becomes a Candidate, increments the term, and asks the other 3 for votes.

Nodes 2, 4, and 5 haven't voted this term yet, and Node 3's log is up to date. They grant their votes. Node 3 becomes the new leader with 4 votes (including its own). The whole process takes roughly one election timeout period.

During this window (a few hundred milliseconds), the cluster cannot process writes. Reads might still work from followers depending on consistency settings. Once the new leader is established, writes resume.

If the old leader comes back online, it discovers the new term number, realizes it's been deposed, and demotes itself to follower. The term number is the tiebreaker, and the transition is automatic.

Not every system needs leader election. Amazon's original Dynamo paper (2007) popularized leaderless replication, where any node can accept writes and conflicts are resolved later using techniques like vector clocks and last writer wins.

Cassandra adopted this model. So did Riak. The trade off: higher availability (no election downtime, no single point of failure) but weaker consistency (conflicting writes happen and must be resolved).

DynamoDB (the AWS managed service inspired by the Dynamo paper) actually moved away from leaderless replication. AWS switched DynamoDB to Multi Paxos with a single leader per partition because they wanted to offer strong consistency. The original leaderless design made strong consistency too expensive to guarantee.

When consistency matters, most teams end up choosing a leader.

→ Find me on : Social Links

That’s it for today, keep learning!
Scortier, Signing Off!