The Two Generals Problem Explained
On this page
The Two Generals problem
Two armies camp on hills on either side of a valley, with the enemy city between them. They win only if they attack at the same time; either one attacking alone is destroyed. The generals communicate only by messengers who cross the valley and may be captured.
General A sends: "Attack at dawn." Will A attack? Only if A knows B received the message. So B sends back: "Agreed." Now B won't attack unless B knows A got the confirmation. So A confirms the confirmation. And so on.
Why no protocol can guarantee agreement
Suppose some protocol guarantees agreement with a finite number of messages, and consider the shortest one that works. Look at its last message. The sender's decision can't depend on whether it arrives, because the sender never learns. So the protocol works just as well without that message. But then there's a shorter working protocol, contradicting "shortest". Repeat the argument down to zero messages, which obviously can't produce agreement. So no finite protocol guarantees it over an unreliable channel.
The point isn't generals. It's this: over a link that can lose messages, two parties can never be certain they agree. More acknowledgments raise confidence but never reach certainty.
Where it shows up: TCP, payments and distributed commits
- TCP's connection close. Each side sends FIN and acknowledges the other's. The final ACK might be lost, which is why the side that closes first waits in
TIME_WAITbefore forgetting the connection: a practical hedge, not a guarantee. - "Did my payment go through?" A client sends a charge and the response is lost. The client can't know whether to retry (Day 1).
- Distributed commit. Several databases agreeing to commit together face the same uncertainty, which is why two-phase commit can block (Day 22).
How real systems cope with uncertain delivery
Since certainty is impossible, systems make uncertainty harmless or resolvable:
- Idempotent operations with retries. If doing something twice has the same effect as once, the sender can retry until it gets an answer (Day 21). The uncertainty stops mattering.
- A single source of truth to ask later. Store the outcome durably, and let a confused party query it: "what happened to payment 7f3c?"
- Probabilistic confidence. Enough retries over enough paths make failure unlikely enough to accept.
- Reconciliation. Compare records afterwards and fix differences, as banks do with daily settlement.
The Two Generals problem assumes the messengers can fail but the generals are honest. When nodes may also behave arbitrarily or maliciously, the problem is harder still: that's the Byzantine Generals problem, relevant to blockchains and safety-critical systems, and beyond this course.
Check yourself
The last message in any exchange might be lost without its sender knowing, so the sender of the final message is always uncertain.
They make the charge idempotent with a unique key so the client can safely retry, and store the outcome so it can be queried.
The final acknowledgment of a connection close might be lost, so the closing side waits a while to handle a retransmitted FIN rather than assuming agreement.
Assume any request might have taken effect even when you got no response. Design operations to be safely retried, for example with idempotency keys, and give clients a way to look up the outcome.
It's related but simpler: two parties trying to agree over an unreliable channel. Consensus generalizes agreement to many nodes that can crash, and it's possible under timing assumptions, whereas two-party agreement with guaranteed certainty over a lossy channel is not.