Before distributed systems had servers, brokers, databases, and cloud regions, the fundamental coordination problem could already be described with two armies and an unreliable messenger.
The problem
Two generals are positioned on opposite sides of a city. They can win only if both armies attack at the same time. If one attacks alone, that army will be defeated.
Their only communication channel is a messenger who must cross hostile territory. The messenger may arrive, or may be captured without either general knowing what happened.
General A sends: “Attack at dawn.” General B receives the message and replies: “Confirmed.” But now B does not know whether the confirmation reached A. A can acknowledge B’s confirmation, but then A does not know whether that new acknowledgement reached B.
Every additional confirmation creates another final message whose delivery remains uncertain.
The impossibility
No finite message exchange can create perfect common certainty when any message may be lost. Assume a protocol succeeds after a finite number of messages. Its final message must be necessary; otherwise it could be removed. But if that final message is lost, the required shared certainty is not established. Adding another acknowledgement only moves the same uncertainty to a new final message.
This is not a missing algorithm waiting to be invented. Under the stated assumptions, the uncertainty cannot disappear.
The software version
Consider a client sending a payment request:
- The server receives the request.
- The server commits the payment.
- The response is lost or the connection fails.
- The client observes a timeout.
The client cannot distinguish between two materially different outcomes:
- The server never processed the request.
- The server processed it, but the response did not arrive.
A retry may be necessary, but an unsafe retry may execute the payment twice. TCP can provide an ordered and reliable byte stream while the connection remains usable; it cannot prove the final business outcome after communication becomes ambiguous.
How real systems manage it
Production systems do not solve the paradox. They design around it using explicit guarantees and recovery mechanisms:
- Idempotency keys make repeated requests represent one logical operation.
- Deduplication identifies requests or messages already processed.
- Durable status records let clients query the outcome after a timeout.
- Retries with backoff handle transient failures without uncontrolled load.
- Reconciliation detects and repairs differences that remain after partial failures.
These mechanisms do not create absolute knowledge. They reduce the operational risk and make uncertain outcomes safe to revisit.
The engineering lesson
Reliable distributed systems are not systems in which uncertainty never occurs. They are systems whose contracts, state transitions, and recovery procedures remain correct when uncertainty occurs.
We made it rare enough, controlled enough, and hidden enough that most users never notice it.
The impossibility argument appeared in Some Constraints and Tradeoffs in the Design of Network Communications by E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber in 1975. The scenario is also known as the Coordinated Attack Problem.