Consensus Algorithms

01Overview

Lamport wrote Paxos in 1989 but it was not published until 1998. Paxos reaches agreement among a majority in two rounds of voting and tolerates a minority of failures. It is famously hard to understand, and real implementations are usually heavily simplified.

In 2014 Ongaro and Ousterhout proposed Raft, splitting consensus into leader election, log replication and safety, and putting comprehensibility first. Raft was adopted by etcd, Consul and TiKV. Today consensus algorithms are the invisible skeleton of cloud infrastructure — every configuration change, every failover runs on one.

02History

1989
Paxos is written
Lamport's consensus algorithm.
1998
Paxos is published
The paper appears nine years late.
2014
Raft
Designed for understandability.
2014
etcd adopts Raft
The configuration backbone of Kubernetes.

03Core concepts

Quorum

A majority suffices to commit, tolerating a minority of failures.

Log replication

Copy the same sequence of operations to every state machine.

Leader election

Choose a new coordinator after the leader fails.

04Hands-on

Do it once — it beats reading it ten times

Implement Raft leader election for three nodes and force two failovers, checking the log stays identical

Tick this once you have built it and written down what you learned; the topic is then marked as built.

05Self-check

Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.

Can you explain "Quorum"?

A majority suffices to commit, tolerating a minority of failures.

Can you explain "Log replication"?

Copy the same sequence of operations to every state machine.

Can you explain "Leader election"?

Choose a new coordinator after the leader fails.

What problem did it solve, and why was there nothing better at the time?

Go back to the history section: how was this done before, and what did it cost?

If you had to build it today, how would you break it down?

Use the hands-on task above: write a plan of at most three steps before you start.

06Key people

Leslie Lamport

1941 –

Author of Paxos.

Diego Ongaro

1985 –

Co-designer of Raft.

07Further reading

Paxos Made SimpleLeslie Lamport · 2001
In Search of an Understandable Consensus AlgorithmOngaro & Ousterhout · 2014