Agreement Without A Boss

What Consensus Means

In week 2 you saw that machines fail and messages go astray. Yet many jobs need all machines to settle on one answer: which transaction came first, who holds the lock, what the current balance is. Reaching one shared answer despite failures is the consensus problem.

A consensus protocol must satisfy three properties. Agreement: no two working machines decide different values. Validity: the decided value was proposed by some machine, so the group cannot invent a value from nowhere. Termination: every working machine eventually decides.

Agreement and validity are called safety properties: they say that nothing bad happens. Termination is a liveness property: it says that something good eventually happens. A protocol that never decides is safe but useless, and a protocol that decides quickly but wrongly is live but dangerous. Good protocols protect safety always and deliver liveness whenever the network behaves well enough.

In 1985 Michael Fischer, Nancy Lynch and Michael Paterson proved a famous limit, now called FLP. In a fully asynchronous network, where messages can be delayed without bound, no deterministic protocol can guarantee termination if even one machine may crash. Practical protocols live with this by using timeouts and, when the network is slow, giving up liveness for a while without giving up safety.

Replicated State Machines

Why do we want consensus? The most common reason is the replicated state machine. Suppose several servers each run the same program, and the program is deterministic: given the same inputs in the same order, it produces the same results. If all servers receive the same list of commands in the same order, they stay identical.

Consensus supplies that shared order. The servers agree, one command at a time, on a log: an ordered list of commands. Each server then applies the log to its own copy of the data. If one server dies, the others continue, and when it returns it catches up by reading the log.

This idea sits under many databases and coordination services, and later under blockchains, where the log is the chain of blocks and the state machine is a ledger.

Majorities And Quorums

The central trick of crash-tolerant consensus is the majority quorum. A quorum is a group of machines whose approval is enough to decide. If a quorum is any majority, then any two quorums must share at least one machine. That shared machine remembers the earlier decision and stops a conflicting one.

Take five machines. A majority is three. Two different groups of three, drawn from five, always overlap. So if one group decided value A, any later group must include someone who knows about A.

This also gives the fault tolerance rule. To survive f crashed machines, the system needs at least 2f+1 machines, because the remaining f+1 still form a majority. Five machines survive two crashes. Three survive one. Four machines survive only one, the same as three, which is why consensus clusters use odd sizes.

A minority partition cannot decide anything. This ties directly to the CAP theorem from week 2: a majority-based system gives up availability on the minority side to stay consistent.

Paxos In One Page

Leslie Lamport devised Paxos in the late 1980s and described it with a story about priests on a Greek island, a paper published in 1998. The idea is so useful that most later protocols are variations. Lamport later wrote 'Paxos Made Simple' (2001) with a plain account.

Paxos decides one value through two phases. Machines play roles: proposers suggest values, acceptors vote, and learners find out the result. In the first phase, a proposer picks a number n and asks a majority of acceptors to promise not to accept any proposal numbered lower than n. The acceptors also report any value they have already accepted. In the second phase, the proposer asks the majority to accept a value. If an acceptor had already accepted something, the proposer must propose that earlier value with the highest number, not its own. This rule is the heart of the protocol: it carries an earlier decision forward and so protects agreement.

Paxos is correct but famously hard to teach and hard to turn into a full system. Real services need a sequence of decisions, leader handling and membership changes, and the original description leaves many such gaps to the implementer.

Raft: Consensus Designed To Be Understood

Diego Ongaro and John Ousterhout designed Raft in 2014 with a goal stated in the paper title: 'In Search of an Understandable Consensus Algorithm'. Raft breaks the problem into three parts.

Leader election. At any moment, each server is a follower, a candidate or the leader. The leader sends regular heartbeat messages. If a follower hears no heartbeat for a random timeout, it becomes a candidate, adds one to its term number (a counter of elections) and asks others for votes. A candidate that wins votes from a majority becomes the leader. Random timeouts make split votes rare.

Log replication. Clients send commands to the leader. The leader appends the command to its log and sends it to the followers. When a majority has stored the entry, the leader marks it committed and applies it, and the followers follow. A committed entry is never lost, because any future leader must have been elected by a majority that overlaps the majority that stored the entry.

Safety rules. A server votes only for a candidate whose log is at least as up to date as its own. This ensures that a new leader already holds every committed entry. Raft is widely used. The coordination stores etcd and Consul and many databases run on Raft.

The Byzantine Generals Problem

Paxos and Raft assume machines either work correctly or stop. Real systems can contain machines that behave arbitrarily: a bug sends corrupt data, an intruder takes control, or an owner acts out of self-interest. Engineers call arbitrary misbehavior a Byzantine fault.

Leslie Lamport, Robert Shostak and Marshall Pease described this in a 1982 paper using a story. Several generals surround a city. They must all attack together or all retreat, and they communicate by messengers. Some generals may be traitors who send different messages to different people. How can the loyal generals reach the same plan?

The paper's result is exact. With oral messages, agreement is possible only if fewer than one third of the generals are traitors. To tolerate f traitors, you need at least 3f+1 generals. With three generals and one traitor, the loyal general cannot tell who lies, because each of the other two accuses the other.

Compare this with crash faults. Crash tolerance needs 2f+1 machines, while Byzantine tolerance needs 3f+1. The extra machines pay for the possibility of lying.

Byzantine Fault Tolerant Protocols

Miguel Castro and Barbara Liskov's PBFT (Practical Byzantine Fault Tolerance, 1999) showed that a Byzantine-tolerant protocol can run fast enough to be useful. With 3f+1 replicas, a leader proposes an order for requests, and replicas exchange several rounds of messages. A replica acts only after seeing agreement from 2f+1 replicas, so any two such groups overlap in at least one honest replica.

Signatures help, since a signed message proves who said what, and a traitor cannot forge another machine's words. Digital signatures are the subject of week 6.

PBFT has a cost. Every replica talks to every other replica, so the number of messages grows with the square of the group size. This keeps classic BFT groups small, often a few dozen machines, and every participant must be known in advance.

Bitcoin, announced by Satoshi Nakamoto in 2008, solved Byzantine agreement among unknown and open participants with a different tool: proof of work, in which the right to add a block is earned by spending computing effort. Later systems use proof of stake and BFT-style voting among validators. These designs appear again in the weeks after this one. The trade-off to remember: known members allow quick, certain agreement, and open membership needs extra machinery to resist fake identities, as week 3 described.

Choosing A Design

Ask who the machines belong to and what failures you expect. If one organization owns all machines, crash faults are the realistic worry, and Raft is a sound and simple choice. If several organizations that do not fully trust each other run the machines, Byzantine faults are a real concern, and a BFT protocol fits better. If anyone may join, you need a protocol designed for open membership.

Also ask what you give up. Majority protocols stop on the minority side of a partition. BFT protocols need more machines and more messages. In every case, agreement takes at least a few network round trips, so the latency floor from week 2 applies.

Next week we use agreement to protect data itself, and learn how to name content by its fingerprint.

Key Terms

Consensus

Agreement among machines on a single value despite failures.

Safety property

A guarantee that nothing bad happens, such as two machines deciding different values.

Liveness property

A guarantee that something good eventually happens, such as every machine deciding.

Quorum

A group of machines whose approval is enough to make a decision.

Replicated state machine

Several servers that apply the same ordered list of commands to stay identical.

Leader election

The process by which a group chooses one machine to coordinate decisions.

Term

In Raft, a counter that numbers each election period.

Byzantine fault

A failure in which a machine behaves arbitrarily, including lying.

3f+1 rule

The minimum group size needed to tolerate f Byzantine machines.

Exercise: Quorum And Fault Calculator

1. Create a file named quorum.py and paste the code from the 'How many machines do you need?' slide, extended to also print 3f+1 for the same group sizes.
2. Run it and read the output for group sizes 3 to 10.
3. Write down how many crashes a group of 5 survives and how many Byzantine faults a group of 7 survives.
4. Open raft.github.io (the free Raft visualization) and start a cluster of five servers.
5. Stop the leader and watch a new election. Then stop two more servers and observe what happens when the majority is lost.
6. Write a paragraph explaining why four servers are no better than three for crash tolerance.

Further Reading

• The Byzantine Generals Problem, Leslie Lamport, Robert Shostak and Marshall Pease, ACM TOPLAS, 1982
• In Search of an Understandable Consensus Algorithm (Raft), Diego Ongaro and John Ousterhout, USENIX ATC, 2014
• Paxos Made Simple, Leslie Lamport, ACM SIGACT News, 2001
• Practical Byzantine Fault Tolerance, Miguel Castro and Barbara Liskov, OSDI, 1999
• Impossibility of Distributed Consensus with One Faulty Process, Michael Fischer, Nancy Lynch and Michael Paterson, Journal of the ACM, 1985