Two Generals Problem

The Two Generals Problem is a thought experiment in distributed computing demonstrating that reliable consensus is impossible over an unreliable communication channel. Two allied generals, camped on opposite sides of an enemy city, must coordinate a simultaneous attack — but their messengers may be captured. Every message of confirmation requires another confirmation, producing infinite regress: no finite exchange of messages can guarantee that both generals know the other is ready to attack at the agreed time.

The problem was formalized in the 1970s and proved a foundational result: no consensus protocol can guarantee agreement in the presence of message loss, even between just two parties. It is the logical precursor to the Byzantine Generals Problem and the practical motivator for TCP handshake design. Its connection to common knowledge theory is direct: coordinated attack requires common knowledge of the plan, but common knowledge cannot be created over an unreliable channel in finite rounds.