Top Puzzle 20: The Two-Generals Problem | Puzzles for Interview - Interview Preparation PDF Download

Introduction

The Two Generals’ Problem is a problem in computer science that deals with communication between two parties over an unreliable channel. It is a more specific version of the Byzantine Generals’ Problem.

The Problem

The problem involves two generals, Alice and Bob, who have been ordered to attack and destroy Castle C. However, there are some constraints - Castle C is situated on top of a mountain, and Alice and Bob have each set up camp on opposite ends of the mountain. It is impossible to reach the other end of the mountain without traversing the top. Alice and Bob must attack in unison to be successful. An uncoordinated approach will result in defeat. Alice will decide the timing of the attack and share it with Bob via messenger. Bob will then send a response back to Alice in a similar manner. If consensus is reached, Alice and Bob will attack Castle C together.

Solution

There are multiple scenarios that can be derived from this problem. Suppose Alice sends a message to Bob but doesn’t get a response back. In that case, the messenger encountered trouble either on the way there or back. Alice could send additional messages to Bob, but the results will be inconsistent. The scenario will turn into a game of probability, and the two parties will not be able to reach a consensus. Suppose Alice and Bob successfully send the messenger back and forth. How does Bob know that Alice’s message has not been tampered with? How does Alice know that she has received a clean response from Bob? How does Bob know that his response has been safely delivered to Alice? Alice and Bob will be stuck in an infinite loop, questioning whether consensus has truly been reached. Therefore, it is impossible for two parties to establish common knowledge without a reliable method of communication.
Analogy to Computer Science: Let’s replace the armies with computers. If you’ve made a connection to TCP (Transmission Control Protocol), you’re on the right track. TCP relies on a “4-way handshake” to terminate a connection. Computer A sends a FIN message to share its intent to terminate. Computer B responds with an ACK message and then a FIN. Computer A then sends an ACK message of its own. A total of four messages are exchanged to confirm a termination.

Conclusion

The Two Generals’ Problem is a classic example of the limitations of communication over an unreliable channel. It is essential to have a reliable method of communication to establish common knowledge and reach a consensus.