The Two Generals’ Problem: Why Perfectly Reliable Message Delivery Is Mathematically Impossible
Every retry, every ack, every at-least-once delivery guarantee is built on top of a proof that says the thing you actually want, perfect certainty, can never be reached.
Somewhere underneath every distributed system you’ve ever built sits a small, uncomfortable proof. It doesn’t say reliable messaging is hard. It says perfectly reliable messaging, in the strict sense of both sides being certain the other received the message, is mathematically impossible over a channel that can lose messages, no matter how many messages you’re willing to send.
This is the Two Generals’ Problem, and it’s worth understanding properly, because it’s not a historical curiosity. It’s the reason at-least-once delivery, idempotency keys, and TCP’s own handshake all exist in the form they do.
The Setup: Two Generals, One Coordinated Attack
Picture two generals camped on hills overlooking a valley, with the enemy positioned between them. They can only win by attacking at the exact same time. Attacking alone means certain defeat. The only way to coordinate is to send messengers through the valley, and any messenger might be captured along the way.
The first general sends a message proposing an attack time. But the moment that messenger leaves camp, the first general has no way of knowing whether it arrived. So the second general, upon receiving it, sends an acknowledgment back. But now the second general faces the identical problem: was the acknowledgment received? Whoever sends the last message in the chain can never be sure it got through, and that uncertainty never goes away, no matter how many more messages get added to close the loop.
Why Adding More Acknowledgments Never Fixes It
The instinct is always to add one more confirmation. If the first acknowledgment might not arrive, send a confirmation of the confirmation. But this doesn’t shrink the problem, it just relocates it. Whichever party sends the very last message in the chain is, by definition, the one who never receives confirmation that their message got through. You can extend the chain to ten messages or a thousand, and the final sender is still left in the dark.
This is the actual proof, not an approximation of it: for any finite protocol, there exists a last message, and the party who sent it cannot distinguish between “it arrived and the whole plan succeeded” and “it was lost and the whole plan quietly fell apart.” No amount of finite back-and-forth removes that final leap of faith.
What Practical Systems Do Instead
Real systems don’t solve this. They make the probability of failure small enough that it stops mattering in practice, which is a completely different achievement than solving the impossibility. If each leg of a message exchange succeeds with some independent probability, then stacking more confirmation round trips drives the chance of total failure down sharply, even though it mathematically never reaches exactly zero.
This is exactly the gap between theory and engineering. The proof says certainty is unreachable. Engineering says a failure rate small enough to be negligible is good enough to build a business on, and that distinction is why practical systems layer retries on top of an impossibility result instead of trying to defeat it outright.
Where This Shows Up in Real Systems
The Two Generals’ Problem was first described by E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber in 1975, in a paper examining trade-offs in network communication design, and it was later popularized under its now-familiar military framing by Jim Gray in 1978. Nearly every reliability mechanism in distributed systems today is, in some form, a practical response to that original result.
TCP’s Handshake
TCP’s three-way handshake, SYN, SYN-ACK, ACK, looks like it should resolve the problem, but it doesn’t. It gives both sides reasonable confidence that a connection is established, not a mathematical guarantee. It’s a finite protocol, so it inherits the same last-message blind spot as the generals, just with failure probabilities low enough that nobody notices in ordinary operation.
At-Least-Once Delivery and Idempotency
Message queues and event-driven systems commonly settle for at-least-once delivery: keep retrying until an acknowledgment is received, accepting that a message might occasionally be delivered more than once if the acknowledgment itself gets lost. That’s a direct concession to the impossibility result. Rather than pretending exactly-once delivery is achievable for free, these systems shift the burden onto idempotency, designing the receiving side so that processing the same message twice causes no harm.
A Related but Distinct Result
It’s worth separating this from the FLP impossibility result, published by Fischer, Lynch, and Paterson in 1985, which shows that deterministic consensus cannot be guaranteed in an asynchronous system where even one process might fail. FLP is about a broader consensus setting with process failures, not specifically message loss between two fixed parties, but the two results share the same underlying flavor: in an asynchronous, unreliable environment, some form of perfect coordination that looks achievable on a whiteboard turns out to be provably out of reach.
How Many Retries Actually Buy You
Since certainty is off the table, the real engineering question becomes: how many retries does it take to make failure negligible rather than eliminated? The math here is simple and worth internalizing, because it explains why most production retry policies settle on a small number of attempts rather than an unbounded chain.
| Retry Attempts | Chance All Attempts Fail (at 5% per-attempt failure rate) |
|---|---|
| 1 | 5% |
| 2 | 0.25% |
| 3 | 0.0125% |
| 4 | 0.000625% |
| 5 | 0.00003% |
This is why three to five retries is such a common default across HTTP clients, message brokers, and RPC frameworks. It’s not an arbitrary number. It’s the point at which the remaining risk becomes small enough to accept, given that the underlying impossibility guarantees the risk can never be driven to exactly zero in the first place.
Quick Checklist: Designing Around the Impossibility
- Stop aiming for certainty and start aiming for a failure rate small enough to be acceptable for the use case.
- Make the receiving side idempotent, since retries mean duplicate delivery is always a possibility, not an edge case.
- Decide explicitly whether your system needs at-least-once or at-most-once semantics, since exactly-once is not free.
- Remember that acks and handshakes reduce risk, they don’t eliminate the underlying uncertainty.
- Size your retry count based on the acceptable residual failure probability, not on habit or a copied default.
What We Learned
The Two Generals’ Problem proves something narrow but important: no finite exchange of messages over an unreliable channel can give both sides certainty that the other received the final word. Every retry policy, every acknowledgment, every idempotency key in modern distributed systems exists because that gap can be narrowed but never closed. Understanding the proof changes how you read a retry count in a config file. It stops looking like an arbitrary number and starts looking like an explicit, calculated bet against a form of uncertainty that was never going away in the first place.
