Two generals must attack at the same time to win, but can only coordinate by messengers crossing a valley where some are captured. Can they ever be certain of a shared plan? No — provably. Whoever sends the last message cannot know it arrived, so they need an acknowledgment; but the ack's sender cannot know it arrived, needing an ack of the ack; forever. Guaranteed agreement over an unreliable channel is impossible — the limit that says why every real protocol settles for “probably” instead of “certainly.”
THE TECHNIQUE unreliable channel ⇒ common knowledge unattainable; both-certain is never reached
Run the acknowledgment regress: each message can make its receiver sure of the sender, but the sender of the latest message is always left unsure it arrived — so however many rounds you add, the two are never certain at the same time: live demo
HISTORY & CREDIT Akkoyunlu et al. 1975 · named by Gray 1978
“Send enough acknowledgments and eventually both sides are sure.” — no finite number suffices. Certainty here means common knowledge (I know that you know that I know…), and each message adds only one level; over a lossy channel the tower never tops out. “Enough” does not exist. cited
1975 · Akkoyunlu, Ekanadham & Huber — first state the impossibility (“Some Constraints and Trade-offs in the Design of Network Communications”). 1978 · Jim Gray — gives it the “two generals” framing that made it famous. 1969–90 · common-knowledge theory (Lewis; Halpern & Moses) — formalizes why the infinite tower of “I know that you know” can never be built over a lossy channel.
This is the honest floor of the whole field: distinct from Byzantine faults (lying nodes), this is message loss alone defeating certainty. Every practical protocol lives above this floor by trading certainty for high probability. Two Generals 1975
RECOMMEND FOR I-13 both-certain never reached across any k, computed
On the canonical compiler, running the acknowledgment regress for up to 100 exchanges, the two sides are never simultaneously certain — there is always exactly one dangling, unacknowledged final message:
$ i13 run twogen.i13 # ack regress over 100 exchanges
everBoth = 0 -- never both certain at the same step, for any k
unackedFinal = 1 -- invariant: always exactly one dangling final message
Recommend: the Two Generals is LIT for I-13 — verified that across 100 exchanges the two parties are never both certain (everBoth = 0) and there is always exactly one unacknowledged last message (unackedFinal = 1). The compiler enacts the impossibility as a fixed point that never closes — the reason consensus over a lossy channel buys probability, never certainty.