You text a friend, “Let’s meet in front of the station at 3 p.m. tomorrow,” and when no reply comes, you start to feel uneasy because you don’t know whether they read it. Even if they reply “Got it,” you may now wonder whether they know that you received their reply. In computer science, there is a famous problem that explains this endless loop of confirmations through a story about two generals. It is called the ‘Two Generals’ Problem.’
Put simply, the Two Generals’ Problem is a thought experiment showing that ‘over a communication channel where messages can be lost along the way, two parties can never be perfectly certain that they have agreed on the same action.’ It is a staple when people first learn about networks and distributed systems, and it is regarded as the first computer communication problem to be proven unsolvable.
In this article, we will look in turn at the situation the Two Generals’ Problem describes, why it cannot be solved, where the problem came from, and how real-world technology handles this limit.
The Two Generals’ Problem: Where Confirming the Confirmation Never Ends
What Situation Does the Two Generals’ Problem Describe?
The problem begins with a story about two armies with a castle between them.
(1) Two armies camped apart
Two armies, each led by a general, are camped on different hills, preparing to attack a single castle. If the two armies attack at the same time, they can take the castle, but if only one attacks, that army will suffer a crushing defeat.
(2) A messenger crossing a dangerous valley
The only way the two generals can communicate is by sending a messenger through a valley guarded by the castle’s army. The messenger can be captured at any time, and the sender has no way of knowing whether the messenger arrived.
(3) The certainty the generals want
The generals don’t just want to set a time for the attack; they want to know for certain that ‘both of us will attack at that time.’ Only with this certainty can they move their armies without worry.
In this way, the Two Generals’ Problem condenses into a simple scene the difficulty that arises when two parties try to coordinate their actions over an unreliable communication channel.
Why Can They Never Be Certain?
It might seem that exchanging messengers several times would solve the problem, but adding more confirmations only repeats the same worry.
(1) The anxiety of the first message
Even if the first general sends a messenger saying “We attack at 6 a.m.,” he does not know whether the messenger arrived, so he hesitates for fear of ending up attacking alone.
(2) Replies that go on forever
If the second general sends back a reply saying “Received, we will attack at 6,” now it is the second general who worries about whether that reply arrived. Even if the first general sends another confirmation that he received the reply, that last messenger can be captured too.
(3) The paradox of the last messenger
No matter how many times they exchange messages, the sender cannot know whether the last messenger arrived. Even if the last messenger is captured, the situation looks exactly the same to the sender, so if the decision to attack hinges on that single messenger, one side may end up attacking alone. This leads to the conclusion that no method of exchanging a fixed number of confirmations can perfectly coordinate the two generals.
The key point is that a confirmation message can be lost just as easily as the original message. No matter how many layers of confirmation you stack up, the uncertainty of the very last layer remains.
Where Did the Two Generals’ Problem Come From?
The problem was formulated in the 1970s, when computer networks were just beginning to develop.
- First Publication: In 1975, E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber first presented this problem, along with a proof that it cannot be solved, in a paper on constraints in the design of network communications. In that paper, the situation was described not with generals but with two groups of gangsters trying to communicate with each other.
- Naming: Database researcher Jim Gray called the problem the ‘Two Generals Paradox’ in a 1978 piece on database operating systems, and it became widely known through today’s story of the generals.
- Byzantine Generals Problem: In 1982, Leslie Lamport, Robert Shostak, and Marshall Pease published the ‘Byzantine Generals Problem,’ which deals with a situation where traitors are mixed in among several generals. The Two Generals’ Problem is often introduced as a primer before learning this problem.
How Does Real-World Technology Handle This Limit?
If perfect certainty is impossible, real-world technology chooses to reduce uncertainty to a manageable level rather than eliminate it.
(1) Sending multiple times
If the first general sends several messengers, the probability that all of them are captured drops sharply. It is not certainty, but it can raise the chance of success enough.
(2) Acknowledgment and retransmission
TCP (Transmission Control Protocol), the internet’s basic communication protocol, exchanges three messages when establishing a connection, and after sending data, it sends it again if an acknowledgment of receipt does not arrive within a set time. This approach cannot guarantee that both sides are always in the same state either, but it creates enough reliability for practical use.
(3) Using silence as a signal
Another approach is to agree in advance that if no word comes within a certain period, the other side is deemed to have accepted the plan. This makes it possible to gain a high degree of confidence while sending fewer messengers.
What all these approaches have in common is that they aim for ‘reliable enough’ instead of perfection.
The Two Generals’ Problem reminds us that no matter how sophisticated a technology is, it cannot fully overcome the limits of an unreliable communication channel. The messengers, payment systems, and cloud services we use today are also designed on the basis of accepting this limit.
Accepting that perfect certainty is impossible and building safeguards on top of that fact: this is the first step in designing a system people can trust.
