Why Consensus Is Hard: FLP, Two Generals and Paxos

Different servers start giving different answers for the same thing, and nobody can tell which answer is right. It happens because messages between servers can be lost or late, and a silent server might be dead or just slow. By the end of this guide, you will have Paxos explained step by step.

Picture a common setup. A team runs a configuration store: a service that keeps settings, such as feature flags and upload limits, for many apps. Every setting is copied to five servers, so one dead machine does not take settings offline. The setup is made up, but the problem is real.

One afternoon a network switch splits the five servers into a group of three and a group of two for about 40 seconds. Two admins change max_upload_mb during those seconds, one on each side. The store simply keeps the latest write each side sees.

When the network heals, three servers say 80 and two say 50. Apps get a different upload limit depending on which server they ask. The naive fix sounds easy: just make the servers agree.

Making them agree is called the consensus problem. Three famous results show what agreement can never promise, and Paxos is the classic algorithm that still keeps it safe. This guide follows the same five-server store through all four.

Consensus is getting several servers to pick one value and never change their minds, even when some of them crash. In the store, the value is the next setting, such as max_upload_mb = 80.

Replica. A replica is one of the servers that holds a copy of the data. The store runs five replicas, named R1 to R5.

Quorum. A quorum is a group big enough to make a decision. Classic Paxos, as Paxos Made Simple describes it, uses a majority, which for five replicas means any three. Any two majorities of the same five servers share at least one server.

Safety. Safety means nothing bad ever happens. For consensus, the bad thing is two replicas deciding on different values, like 80 and 50.

Liveness. Liveness means something good eventually happens. For consensus, the good thing is that some value actually gets decided, instead of the servers talking forever.

Asynchronous. An asynchronous system makes no promise about timing. A message may arrive in a millisecond or in an hour, and a server may pause for any length of time.

Crash fault. A crash fault means a server stops, and maybe restarts later, but never sends wrong information. Lying is a different, harder kind of fault, covered below.

The Two Generals problem is a thought experiment showing that two parties cannot be certain they agree when any message between them might be lost. No number of acknowledgements fixes it.

Picture two hill forts in the Sahyadri, on either side of a deep valley. They can win only if both garrisons march at the same dawn. The only way to talk is a messenger who walks down through the valley and up the other side. Any messenger might be caught on the way.

The first fort sends: march at dawn on Tuesday. If the messenger is caught, the second fort never hears it. So the first fort asks for a reply. The second fort sends one, but now it worries. If its reply was lost, the first fort will stay home, and marching alone means defeat.

Follow the chain below. Each box is one trip across the valley, and each trip leaves the sender of that trip unsure.

The proof idea is short. Suppose some plan works with a fixed number of messages, and look at the very last one. Its sender cannot see whether it arrived, so the sender must act the same either way.

The receiver must then act the same too, or the two would disagree whenever that message is lost. So the last message was not needed. Remove it and repeat, and you end with no messages at all, which cannot work.

The forts are the one picture this guide uses. Where the picture breaks: a lost battle cannot be undone, but many computer actions can be checked, retried or reversed later. Martin Kleppmann's Cambridge lecture notes make this point with an online payment.

The store meets this problem on every write. If the reply to a write is lost, the client cannot tell whether the write happened. So clients retry with a request id, and the store ignores repeats.

The Byzantine Generals problem asks how loyal generals can agree on a plan when some generals are traitors who tell different stories to different people. Its answer is that you need far more honest members than liars.

Leslie Lamport, Robert Shostak and Marshall Pease published it in 1982. Their generals camp around an enemy city, talk only by messenger, and some may be traitors.

Their main result is precise. With oral messages, whose contents are completely under the sender's control, agreement is possible only if more than two thirds of the generals are loyal. So no solution with fewer than 3m + 1 generals can cope with m traitors.

With unforgeable signed messages, the paper shows the problem can be solved for any number of traitors. Both results assume every message arrives and a missing message can be noticed. That is a world with timing promises, unlike the asynchronous one below.

In server terms, a Byzantine fault is any wrong behaviour, not just stopping. A buggy or hacked replica might tell R1 the value is 80 and tell R2 it is 50.

The store does not pay for this. Its replicas run on machines the team controls, with checksums (small fingerprints that reveal corrupted data) on stored data. So it assumes crash faults only. Paxos Made Simple assumes the same, calling its setting the asynchronous, non-Byzantine model.

Tolerating liars costs more. Practical Byzantine Fault Tolerance (PBFT), by Miguel Castro and Barbara Liskov in 1999, uses 3f + 1 replicas to survive f faulty ones. Here f plays the same role as m above. The paper says that is the minimum for an asynchronous system.

The FLP result says that in a fully asynchronous system, every deterministic consensus method has some run that never finishes, even if only one process may crash. Michael Fischer, Nancy Lynch and Michael Paterson published it in 1985.

Deterministic means the method always takes the same step given the same state and the same message. The paper models every process this way.

Their setting is generous on purpose. The network delivers every message correctly and exactly once, no process lies, and at most one may crash. Even so, every such protocol can be kept from finishing.

What makes it hard is the missing clock. The paper gives processes no synchronised clocks and no way to detect a crash. So no server can tell whether another has died or is just running very slowly.

Picture the store's five replicas in the middle of a vote when R5 goes quiet. They cannot tell whether R5 crashed or is just slow. Waiting may mean waiting forever, so a sensible method moves on without it. But the network may delay any message, not only R5's. The proof shows that delaying one message at a time, stage after stage, can keep the outcome undecided forever, even though every message eventually arrives.

• FLP does not say consensus never works. The store reaches agreement on every write while the network behaves reasonably.
• It says no deterministic method can guarantee both safety and termination in a purely asynchronous model with one possible crash.
• So real systems keep safety always, and get progress by adding timing, such as timeouts, or randomness.

The paper's own conclusion points at one way out: require termination only with probability 1. That is where randomised methods come in.

Paxos reaches agreement in two rounds of messages. First a proposer reserves a proposal number with a majority, then it asks that majority to accept a value. Once a majority accepts the same numbered proposal, the value is chosen for good.

Lamport describes three roles in Paxos Made Simple, his 2001 paper. A proposer suggests a value. An acceptor votes on proposals. A learner finds out which value was chosen. In the store, every replica plays all three roles.

The paper lets servers stop and restart, and lets messages be lost, duplicated or late, but never corrupted. That matches the store's world.

Phase 1: prepare and promise

A proposer picks a proposal number n and sends a prepare request to a majority of acceptors. An acceptor replies with a promise if n is higher than any prepare number it has already answered. The promise says it will not accept any proposal numbered below n. It also reports the highest-numbered proposal it has already accepted, if any.

Phase 2: accept and choose

If a majority promises, the proposer sends an accept request with number n and a value v. Here is the rule that makes Paxos safe: v must be the value of the highest-numbered proposal any promise reported. Only if no promise reported a value may the proposer use its own.

An acceptor accepts unless it has already promised a number higher than n. When a majority accepts the same proposal, that value is chosen. Learners then hear it from the acceptors, or from one distinguished learner that collects the votes.

Follow both phases below. The arrows back to picking a higher number show how a beaten proposer tries again.

The acceptor in Python

Here is an acceptor, kept small. save_to_disk is a stand-in that does nothing here. A real acceptor writes its promise and accepted value to stable storage, such as a file that survives a crash.

def save_to_disk(promised, accepted):
    pass  # stand-in: a real acceptor writes both to stable storage here


class Acceptor:
    def __init__(self):
        self.promised = 0         # highest prepare number answered
        self.accepted = None      # (number, value) or None

    def on_prepare(self, n):
        if n > self.promised:
            self.promised = n
            save_to_disk(self.promised, self.accepted)
            return ("promise", n, self.accepted)
        return ("reject", self.promised)

    def on_accept(self, n, value):
        if n >= self.promised:
            self.promised = n
            self.accepted = (n, value)
            save_to_disk(self.promised, self.accepted)
            return ("accepted", n)
        return ("reject", self.promised)

Two lines carry the idea. The promise returns self.accepted, so a new proposer learns what may already be chosen. The test n >= self.promised means an acceptor refuses only proposals older than its promise.

Both methods save before they reply, because Paxos Made Simple requires an acceptor to remember its state even if it fails and restarts. Suppose R3 promised 14, crashed and came back with nothing saved. It would then accept proposal 11, which it had promised to refuse.

We checked both cases on the code above. An acceptor that remembers 14 returns ('reject', 14) for accept(11). A fresh one returns ('accepted', 11).

Paxos stops two values winning because any two majorities share at least one acceptor. That shared acceptor reports the earlier accepted value, and the new proposer must carry that value forward instead of its own.

Replay the split with Paxos. Each replica draws proposal numbers from its own set, so no two replicas ever use the same number.

1. 1

   R1 proposes 80

   R1 sends prepare(11) to R1, R2 and R3, on the bigger side of the split. None has promised a higher number or accepted a value, so all three promise.

2. 2

   80 is chosen

   R1 sends accept(11, 80). R1, R2 and R3 accept it. Three of five is a majority, so 80 is now chosen.

3. 3

   The other side tries 50

   R4 and R5 never heard about it. An admin on their side asks R4 to set the limit to 50. Two of five is not a majority, so 50 cannot be chosen during the split.

4. 4

   The network heals

   R4 sends prepare(14) to R3, R4 and R5. All three promise, because 14 is higher than any number they have answered.

5. 5

   R3 reports the old value

   R3's promise says it already accepted (11, 80). R3 is the server both majorities share.

6. 6

   R4 must propose 80

   The rule forces R4 to send accept(14, 80), not 50. Every replica still agrees on 80. The admin's 50 needs a fresh round of agreement, which the Multi-Paxos section shows.

The second code block holds two helpers and a replay of these steps. Paste both blocks into one file and run it with Python 3.

def choose_value(promises, my_value):
    # promises: one entry per acceptor, either None or (number, value)
    earlier = [p for p in promises if p is not None]
    if not earlier:
        return my_value
    number, value = max(earlier, key=lambda p: p[0])
    return value


def next_number(round_no, replica_id, replicas=5):
    # replica_id is 1 to 5, so each replica's numbers leave a different remainder
    return round_no * replicas + replica_id


# Replay the split: five acceptors named R1 to R5
R = {f"R{i}": Acceptor() for i in range(1, 6)}

n1 = next_number(2, 1)  # R1's number in round 2 is 11
print([R[r].on_prepare(n1) for r in ("R1", "R2", "R3")])
print([R[r].on_accept(n1, 80) for r in ("R1", "R2", "R3")])

n2 = next_number(2, 4)  # after the split heals, R4 uses 14
replies = [R[r].on_prepare(n2) for r in ("R3", "R4", "R5")]
print(replies)
print("R4 must send:", choose_value([rep[2] for rep in replies], 50))

On Python 3.13.16 it prints these four lines:

[('promise', 11, None), ('promise', 11, None), ('promise', 11, None)]
[('accepted', 11), ('accepted', 11), ('accepted', 11)]
[('promise', 14, (11, 80)), ('promise', 14, None), ('promise', 14, None)]
R4 must send: 80

What just happened? Lines one and two are steps 1 and 2: three promises, then three accepts. Line three is step 5, where R3's promise carries (11, 80). Then choose_value returns 80.

It picks 80 because it came from the highest-numbered earlier proposal, not because it is the most common value. In next_number, R1 gets 1, 6, 11, R4 gets 4, 9, 14, and R5 gets 5, 10, 15. We generated 50,000 numbers this way and found no repeats.

When two proposers compete, they can keep cancelling each other forever, so nothing gets chosen. Safety still holds, but liveness is lost. This is the gap FLP predicts, seen in practice.

Lamport's paper walks through it. Proposer p finishes phase 1 with number n1. Proposer q then finishes phase 1 with a higher n2, so p's accept requests fail. Then p tries n3, blocking q, and so on.

We scripted that exact order against the acceptor code above for 20 rounds each. Not one accept request succeeded. With a single proposer, the same acceptors accepted on the first try.

The paper's fix is a distinguished proposer, which most people call a leader. If only one replica proposes, and it can reach a majority with a high enough number, it succeeds. Lamport adds that, because of FLP, electing that leader reliably needs randomness or real time, such as timeouts.

• The store elects one replica as leader. Only the leader proposes new settings.
• Followers expect a heartbeat, a small I-am-alive message, from the leader every 100 ms (made up). After about a second of silence, a follower tries to become leader.
• Each follower waits a random extra delay first, so two of them rarely start at once.
• If the old leader was only slow, nothing breaks. The new leader's higher proposal number simply wins.

Timeouts can be wrong, and two replicas may briefly both believe they lead. Paxos stays safe anyway, because safety never depended on the timeout. The random test in the next section has three proposers starting rounds whenever they like, and safety still held.

Small changes to the rules break safety. Some break it in most runs, but others break it only in rare timings, which is how they survive normal testing. We showed this with a random test of the code above.

The test runs five acceptors and three proposers on one value. Messages arrive in random order, 10% are lost and 5% are duplicated, and acceptors crash and restart. Each run has 400 random steps, and we ran 10,000 runs of each version on Python 3.13.16.

Look at the most-common-value row. It broke safety in 8 runs out of 10,000. At that rate, 300 random test runs catch it only about one time in five.

The one-liar row is the Byzantine problem in miniature. One acceptor that hides its earlier vote breaks the overlap rule, so classic Paxos cannot protect itself from even one liar.

The guide's code also had 7 runs where nothing was chosen within 400 steps. Safety held, but progress did not, which is FLP and duelling proposers again.

Zero violations is evidence, not proof. Paxos is safe because of Lamport's argument; the test only shows this code matches it under the timings we tried.

Multi-Paxos runs one Paxos instance for each slot in an ordered log of commands, and lets a stable leader skip phase 1 for most of them. Every replica applies the log in the same order, so all replicas end in the same state.

Paxos Made Simple calls this implementing a state machine: a deterministic program that ends in the same state whenever it runs the same commands in the same order. Each log slot in the store holds one command, such as set max_upload_mb to 50.

Follow a write below from the admin, through the leader, to the replicas and the log.

Skipping phase 1 is the big speed win. Paxos Made Simple says a new leader runs phase 1 once for all future slots, so each command then costs only phase 2.

Paxos Made Live, from the Google engineers who built a Paxos-based log for the Chubby lock service, describes the same trick. It calls phase 1 messages propose messages, and says they may be left out while the coordinator, their word for the leader, stays the same.

The same paper is honest about the gap between the algorithm and a working system. Its authors write that building a fault-tolerant database on Paxos proved non-trivial, despite the existing literature.

• Disk corruption. A replica that loses its saved state may go back on earlier promises, the same bug as the forget-on-restart row. It rejoins as a non-voting member until it has seen one complete Paxos instance.
• Master leases. Reads cannot simply come from the master's own copy, because another replica may have taken over. Sending every read through Paxos is expensive, so they added leases: a time-limited right for the master to answer reads alone.
• Testing. Their tests inject random failures chosen by a random number generator whose seed is given at the start. So any failing run can be repeated and debugged.

Paxos is famous because it keeps replicas safe under crashes, lost messages and delays, with a proof, and production systems such as Google's Chubby were built on it. It is hard because the core is tiny while a real system needs much more.

Lamport submitted The Part-Time Parliament to ACM Transactions on Computer Systems in 1990. He told the algorithm as the story of a parliament on an ancient Greek island called Paxos. In his notes, he says the referees wanted the Paxos story removed, and he did nothing with the paper.

It was finally published in May 1998. At the PODC 2001 conference on distributed computing, tired of hearing that Paxos was hard to understand, he wrote Paxos Made Simple. Its abstract is one sentence: the algorithm, presented in plain English, is very simple.

Three reasons it still feels hard:

• Basic Paxos decides one value. A real store also needs a log, a leader, reads, snapshots and membership changes, which Paxos Made Live had to design on top. Snapshots are compact copies that let the log be trimmed; membership changes add or remove replicas.
• The rule that a proposer must adopt the earlier value feels strange until you have traced a split by hand.
• Bugs hide in rare timings. The most-common-value bug above broke safety in only 8 of 10,000 random runs.

Raft, published in 2014 by Diego Ongaro and John Ousterhout, was designed to be easier to understand. Its paper says it produces a result equivalent to Multi-Paxos and is as efficient. The separate Raft guide covers it step by step.

A Paxos cluster needs 2f + 1 replicas to survive f crashed ones, because a majority must still be alive. Three replicas survive one failure, and five survive two. The Raft paper calls five a typical number for that reason.

The team picked five, so it can take one machine down for planned maintenance and still survive one surprise crash. Seven would survive three, but each write would then need four acceptances instead of three.

Even numbers buy no extra crash tolerance. Four replicas need three for a majority, so they survive only one failure, like three replicas do. That is why consensus clusters usually come in odd sizes.

Explain Paxos as a majority vote with numbered proposals, then show why it is safe and what it needs to make progress. Interviewers care more about the trade-offs than about every message name.

1. 1

   State the problem

   Several replicas must agree on each change, even when some crash or the network splits. Say you assume crash faults, not lying servers.

2. 2

   Name the limits

   Mention Two Generals for lossy links and FLP for timing. Conclude that you keep safety always and use timeouts for progress.

3. 3

   Walk through the two phases

   Prepare and promise with a number, then accept with a value. A majority accepting the same proposal makes it chosen.

4. 4

   Show the safety rule

   Any two majorities overlap, and a new proposer must adopt the highest-numbered earlier accepted value.

5. 5

   Add a leader and a log

   Multi-Paxos uses one stable leader to avoid duelling proposers, skips phase 1, and fills an ordered log of commands.

6. 6

   Size and place the cluster

   Use 2f + 1 replicas, usually 3 or 5, spread across zones. Note that each write waits for a majority.