Two Generals Problem

Pradeep P
2 days ago
3 min read

Series: Modern System Design · Layer 3 — Reliability

Layer 3 · Post 15 of 21

← Previous: Backends for Frontends → Next: Byzantine Generals Problem

Layer 3 — Reliability · Post 99 of 119

If messages can be lost, two parties can never be sure the other got the last ack — so they cannot coordinate an attack (or a commit) with certainty.

What you'll learn

The thought experiment, and why "one more ack" never ends
What this forbids (perfect agreement over a lossy channel) and what it does not
Why timeouts, retries, and idempotency are how we live with it

The idea in one minute

Two generals sit on hills. They must attack at the same time. The only channel is a messenger who can be captured (message lost). They try to agree a time.

General A sends "attack at dawn." A cannot know it arrived unless B acks. B acks. B cannot know the ack arrived unless A acks the ack. That needs another ack. There is no last message that both can be sure the other has seen, if any message may vanish.

A -- "dawn?" -->  (maybe lost)
A <-- "ok"    --  B  (maybe lost)
A -- "got ok" -->  (maybe lost)
        ...

This is the impossibility of common knowledge over an unreliable network with no shared clock and no third party. TCP cannot "solve Two Generals." It only makes loss rarer and detectable sometimes.

Why it matters

Every "did the payment go through?" after a timeout is Two Generals. The client sent charge. The reply never came. Charge might have happened.

Post 1's food-app example is this problem with a card network. Idempotency (Post 29) and at-least-once (Post 95) are the engineering response: do not require certainty of the last ack; make duplicates safe and eventually learn the truth.

Interviews: they want you to say you cannot have guaranteed simultaneous agreement over a lossy link, then talk timeouts and reconciliation, not "we'll use TCP."

How it works

What is impossible: a protocol that always terminates with both sides knowing the other will act, if any message can be lost and there is no extra channel.

What is possible:

Probabilistic confidence: send 20 messengers; likely one gets through. Not certainty.
A third party / shared disk: both write to a store that has its own consensus (that's a different model — you added a system that also has to survive partitions).
Don't require simultaneous attack. One side acts, the other learns later and compensates (sagas). Or one side is the source of truth and the other retries until it reads success.
Timeouts: treat "no answer" as a defined state (unknown), then query or retry with the same id.

TCP's handshake still has a last ack that can be lost; connections can be half-open. The internet runs anyway because we repair, we do not wait for philosophical certainty.

Not Byzantine. The messengers do not lie; they just disappear. Lying is the next post.

A simple example

App: POST /charges times out after 10 s. Two Generals says you will never invent a header that makes this timeout impossible.

Correct product:

Client used Idempotency-Key: abc.
On timeout, client does not invent a new charge; it GETs charge abc or retries the same key.
If the server processed it, the retry is a no-op. If not, it processes once.
Ops still have a reconciliation job for the cases that look stuck.

Incorrect: "The TCP stack guarantees the bank and I agree." The bank is another general. The timeout already happened.

Common mistakes

"We'll add an ack of the ack." Infinite regress. That is the proof sketch.

Using Two Generals to refuse all distributed work. We ship packages and payments anyway. We accept unknown and converge.

Confusing it with FLP or Byzantine. Two Generals is two parties, lossy links, coordinated action. FLP is async crash consensus. Byzantine is liars. Different tools.

Treating a 200 OK as cosmic truth. The client crashed before seeing it. The other general is sure; this one is not. Idempotent replay.

How this shows up in real systems

Payment APIs, stock exchanges, airline booking: idempotency keys and "query by id."
SMTP, webhooks: at-least-once; receivers dedupe.
TCP, Kafka acks: reduce uncertainty; they do not create common knowledge after a partition.
2PC: tries to get many generals to commit; still blocks or needs extra assumptions (later posts).

Recap

Over a lossy channel, two parties cannot know they both have the last word.
Production answer: idempotent retries, query the source of truth, reconcile.
Next: when some "generals" lie — Byzantine Generals.