The idea: agreeing over a link you cannot trust
Two armies camp on two hills with the enemy in the valley between them. If both attack at dawn they win; if only one attacks, it is destroyed. The only way to talk is to send a messenger through the valley, and any messenger can be caught. This is the Two Generals problem: can the generals ever be sure they will both attack? The answer is no, for every protocol, however many acks it sends.
The page runs a protocol of 1 to 4 messages. Odd messages go from A to B, even ones back. A message is sent only after the one before it arrived. The rule for both generals: attack only if every message addressed to you arrived.
The last messenger
Look at the last message of any protocol, say #3 from A. A sends it and hears nothing more. Whether #3 arrived or was caught, A sees exactly the same thing: it sent #3, and that is all. So A must act the same in both runs. If A attacks, then in the run where #3 is caught B holds, and A attacks alone (Demo 4: ack of the ack, lose the last one). If A would hold, then #3 changes nothing for A, so the protocol works just as well without it, and the same argument applies to #2, then #1, down to a protocol with no messages at all, which certainly cannot coordinate an attack.
Even when nothing is lost (Demo 1: one messenger gets through), the sender of the last message attacks without knowing whether the other side will. The generals win only by luck.
More acks do not help
Each ack adds one level of knowledge: after #1 "B knows the plan", after #2 "A knows B knows", after #3 "B knows A knows B knows". Agreement that both can rely on would need this to go on forever (logicians call it common knowledge). With a fixed number of messages, here is what the rule does:
| caught | 1 message | 2 messages | 3 messages | 4 messages |
|---|---|---|---|---|
| none | both attack | both attack | both attack | both attack |
| #1 | A alone ✗ | both hold | both hold | both hold |
| #2 | – | B alone ✗ | both hold | both hold |
| #3 | – | – | A alone ✗ | both hold |
| #4 | – | – | – | B alone ✗ |
Losing an early messenger is harmless: the rest are never sent and both hold (Demo 5: lose an early messenger: both hold). Losing the last one always splits the generals (Demo 2, Demo 3, Demo 4). A different rule only moves the bad run somewhere else; the argument above covers every rule.
FLP: slow or dead?
The Two Generals problem has a lossy link. Fischer, Lynch and Paterson (1985) asked a harder question with a reliable one. In an asynchronous network every message arrives, but there is no bound on how long it takes, and nodes have no clocks to measure it. If even one node may crash, no deterministic algorithm can guarantee that all live nodes reach the same decision in finite time. This is the FLP impossibility.
The page shows the heart of it with two nodes. A votes attack, B votes hold, and the rule is "attack only if both voted attack". A's vote reaches B at t = 1, so B can decide HOLD at once. A has to hear from B, and it hears nothing: B is either slow (its vote arrives at t = 6) or crashed. The two cases look exactly the same to A, so A must pick one rule for both (Options: FLP, B is, A's rule):
| B is | A waits forever | A times out at t = 3 |
|---|---|---|
| slow | both HOLD at t = 6 | A ATTACK, B HOLD ✗ no safety (Demo 7) |
| crashed | A never decides ✗ no liveness (Demo 6) | A decides alone |
The full proof is more careful: it shows that some starting state is undecided ("bivalent") and that the network can always deliver messages in an order that keeps it undecided. The intuition is the one on the canvas: silence does not tell you why.
How real systems live with it
- TCP does not solve the Two Generals problem. Its handshake and FIN exchange end with a final ACK nobody confirms;
TIME_WAITis there to resend that ACK if the peer asks again. See TCP Handshake. - Retries with idempotency: instead of being sure, resend until you hear back, and make doing the same thing twice harmless. See Idempotency Keys and Retry with Backoff and Jitter.
- Consensus (Paxos, Raft) never gives up safety: a value is chosen only by a majority quorum, so a timeout can never make two nodes decide differently. Timeouts are used only for liveness: to suspect a leader and start a new election. Under partial synchrony (Dwork, Lynch and Stockmeyer, 1988: the network is eventually timely) they always finish; while the network misbehaves they may stall, which FLP says is unavoidable.
- Randomization (Ben-Or) escapes FLP's "deterministic" condition: it terminates with probability 1.
- Two-phase commit picks waiting: a participant that voted yes blocks until it hears from the coordinator, which is the "wait forever" cell of the table.
The CAP theorem is a close relative: during a partition a system must choose between answering (and maybe being wrong) and staying consistent (and maybe not answering).
What the page leaves out
The formal FLP proof (bivalent configurations, the commutativity lemma), more than two nodes and majority quorums, Byzantine generals who lie (see PBFT), failure detectors (Chandra and Toueg) as the formal way to use timeouts, probabilistic protocols that make the bad run unlikely instead of impossible, and real message delays.