The Two Generals Problem

Symptom

You call the payment API. The request goes out. Nothing comes back.

Did the charge happen? You genuinely do not know. Retrying might double-charge the customer. Not retrying might drop the payment. There is no third option available, and no amount of care in your client library creates one.

Or the version in a design doc: the queue promises exactly-once delivery, and you are trying to work out whether to believe it.

Or the version in an incident: the two services disagree about whether an order was placed, and the reconciliation job has been running for three hours.

These are all one problem, and it is provably unsolvable, and knowing that changes what you build instead.

Statement

Two generals must attack a city simultaneously. Attacking alone means defeat. They communicate only by messengers who cross enemy territory and may be captured. Messages that arrive are correct; messages may simply never arrive.

No protocol, using finitely many messages, lets both generals reach certainty that the other will attack.

Note what is not assumed. Nobody is lying. Nobody crashes. There is no Byzantine behaviour, no clock skew, no corruption. The single adversity is that a message may be lost, and that alone is fatal. This is what makes the result so much stronger than its cartoon setting suggests: it is the weakest possible failure model, and it already suffices.

Argument

Suppose a protocol exists that solves the problem. Among all its executions, consider one that succeeds — both generals attack — using the fewest messages. Call that number $n$, and let this shortest successful execution be $E$.

Now consider the last message in $E$, message $n$.

That message might have been lost. The channel offers no guarantee, so there is an execution identical to $E$ in every respect except that message $n$ never arrives.

Consider the sender of message $n$. From their point of view, these two executions are indistinguishable: they sent the message, and in neither case did they receive anything afterward, since message $n$ was the last one. They cannot condition their behaviour on the difference. So they attack in both, or neither.

Since $E$ succeeds, they attack in both. And the receiver, in the execution where the message was lost, has exactly the information they had before message $n$ was sent — so they behave as they would have without it.

So in the lossy execution, both generals still act correctly. But that execution used only $n-1$ delivered messages, and had a successful outcome. So a protocol succeeding with $n-1$ messages exists, contradicting the minimality of $n$.

Therefore no minimal $n$ exists, and therefore no finite protocol exists. $\blacksquare$

The argument is a descent, and the engine is the indistinguishability step: the sender of the final message cannot know it arrived, so the final message can never be load-bearing. Which means no message can be, since removing it just promotes its predecessor to the same position.

The knowledge framing, which is the one that sticks. Write $K_A(p)$ for “A knows $p$”. What coordinated action requires is common knowledge: A knows, B knows, A knows B knows, B knows A knows A knows, forever. Each message buys exactly one more level of that infinite tower:

$$K_A(p),\; K_B K_A(p),\; K_A K_B K_A(p),\; \dots$$

An acknowledgment raises the tower by one. An acknowledgment of the acknowledgment raises it by one more. Common knowledge is the limit, and no finite number of messages reaches a limit. Halpern and Moses proved this precisely in 1990: common knowledge is unattainable in a system with unreliable communication, and coordinated simultaneous action requires common knowledge. That is the general theorem; the two generals is its smallest instance.

Forbids

Exactly-once message delivery. A receiver cannot distinguish “my acknowledgment was lost” from “the sender never sent,” so the sender must choose between resending (at-least-once, risking duplicates) and not resending (at-most-once, risking loss). There is no third protocol. Every queue that advertises exactly-once is doing something else and calling it that; usually at-least-once delivery plus deduplication, which works and is not the same claim.

A distributed transaction with no uncertainty window. Two-phase commit does not solve this. It relocates the uncertainty into the participants after they vote yes, where they must block until the coordinator returns. That blocking window is not a bug in 2PC, it is this theorem showing through (T068, T064).

Guaranteed simultaneous action between two parties over a lossy channel. Including: cutting over two services at the same instant, atomically flipping a feature flag in two regions, and confirming both a charge and a shipment together.

A TCP connection close that both sides agree on. The TCP four-way handshake ends with a TIME_WAIT of twice the maximum segment lifetime, and that timer is not an optimization. It is the protocol admitting it cannot get certainty and substituting a probabilistic wait. The final ACK is unacknowledged, necessarily, because acknowledging it would need an acknowledgment.

Does not forbid

It does not forbid exactly-once semantics, and conflating this with exactly-once delivery is the misreading that generates the most pointless argument on the internet. Kafka’s exactly-once processing is real, works, and does not violate this theorem. It delivers at-least-once and deduplicates using idempotent producers with sequence numbers plus transactional offsets, so the observable effect happens once even though the message may arrive several times. Stripe’s idempotency keys do the same. The theorem forbids certainty about delivery; it says nothing about making duplicate delivery harmless, and that is where the entire practical solution lives.

It does not forbid consensus in real systems, which is the other big one. “Two generals proves distributed consensus is impossible, so Paxos must be snake oil” is a thing said with confidence by people who have read one blog post. Paxos and Raft change the problem in two specific ways: they require only a majority, not all participants, and they drop the requirement of simultaneous action in favour of eventual agreement on an ordered log. Both escapes are legitimate and neither contradicts anything here. What they still cannot do is guarantee progress during an arbitrary partition, which is FLP (T062) and CAP (T066), a different and weaker limitation.

It does not mean retries are useless. They cannot deliver certainty, but each retry raises the probability of delivery. If a message arrives with probability $0.99$, five independent attempts fail with probability $10^{-10}$. That is not certainty and the theorem is untouched, but it is a better failure rate than most hardware you are running on, and “provably impossible” is not a reason to skip the retry loop.

It does not apply to a reliable channel. If message delivery is guaranteed — a single machine’s memory, a synchronous bus, a channel with a known bound on loss — two generals is not a constraint at all. This matters more than it sounds: a great deal of accidental distributed-systems complexity comes from treating an in-process call as if it had the network’s failure model, or worse, the reverse.

It does not apply once you drop simultaneity. Almost every practical fix is this move. Two-phase commit with a timeout, sagas with compensating transactions, eventual consistency, and CRDTs all abandon “both act at the same instant” in exchange for “both converge eventually.” The theorem is specifically about coordinated simultaneous action, and simultaneity turns out to be the requirement almost nobody actually needs once they say out loud why they wanted it.

Boundary

The impossibility is exact, so every workaround is a change of question. There are four, and essentially all production systems use one:

• Idempotency. Make repeated delivery harmless, then use at-least-once and retry freely. You have not solved coordination; you have made the failure to coordinate not matter. This is the single most valuable move in applied distributed systems, and if you take one thing from this post, it is that the right response to “did the payment go through?” is to make asking twice safe rather than to try harder to know.
• Probabilistic certainty. Accept a residual failure probability, retry until it is below your error budget. TCP’s TIME_WAIT, exponential backoff, and every timeout you have ever tuned are this. Note that a timeout is not a measurement, it is a guess with a confidence level.
• Drop simultaneity. Sagas, eventual consistency, CRDTs. Converge instead of agreeing at an instant.
• Drop unanimity. Require a majority rather than everyone, and get consensus in the asynchronous-with-crashes model — Paxos and Raft (T064). This is the deepest of the four and the one that took thirty years to make practical.

What remains genuinely impossible after all four: knowing, right now, with certainty, whether the other side received your message. No system on earth has this, including the one you are working on, and designs that quietly assume it fail in ways that take a long time to diagnose because the assumption is never written down.

Read next