The Two Generals Problem and TCP Three-Way Handshake

The Two Generals Problem, also known as the Two Generals Paradox or the Two Army Problem, is a classic computer thought experiment.

First, to avoid confusion, we need to realize that the Two Generals Problem is related to the Byzantine Generals Problem, but they are not the same thing. The Byzantine Generals Problem is a more general version of the Two Generals Problem, which is often discussed extensively in distributed system fault tolerance and blockchain.

1. The Two Generals Problem

Two armies, stationed on two hills, face the same enemy in a valley. The two generals can only win if they attack at the same time. The only way for the two generals to agree on a time is to send a messenger through the valley, which is in enemy-occupied territory. If the messenger is captured, the message will be lost.

Phenomenon 1: General A first sends a messenger to General B to convey "Attack at 10 pm", but General A does not know whether the messenger can pass through the enemy-occupied area. Because he is worried that he will become the only attacker, General A may hesitate to attack as planned; At this time, General B can send a messenger to confirm receipt after receiving it, but B's messenger may also be captured. Because he is worried that A will retreat because he did not receive the confirmation signal, General B will also hesitate; re-confirmation cannot solve the problem, because the new messenger who re-confirms may also be captured. Therefore, alternating confirmations are endless.

Phenomenon 2: General A sent a messenger, but did not receive a reply after a long time. General A did not know whether his own messenger was captured or General B's confirmed messenger was captured.

We realized that even if both parties repeatedly confirmed that they had received each other's last message, they could not be sure that the other party had reached a consensus with them.

The two generals problem has no solution. The current TCP three-way handshake and four-way wave are engineering solutions (we will talk about this later).

2. Brainstorming on the Two Generals Problem

Many people have tried to solve/mitigate the double general problem and have proposed some practical solutions.

Here we still assume the uncertainty of the channel, the messenger can only be captured but will not betray or tamper with it.

2.1 Shotgun bird hunting

If General A sends 100 messengers (numbered 1 to 100) each time, it is expected that General B will at least receive the message from one messenger.

General B evaluates the reliability of this channel based on the number of messengers received, and also sends an appropriate number of confirmation messengers based on probability.

For example: General A sends 100 messengers, and General B receives information from 10 messengers. General B can basically confirm that the reliability of this channel is 10%, and General B should send at least 10 messengers (according to the probability, 1 messenger will reach the other side).

2.2 Intermittent Retry

The shotgun-shooting posture takes too much time for the messenger, but at least it can help General B increase his confidence and reach a consensus.

There is also a strategy that uses fewer couriers (and can improve the general's confidence). Assuming it takes 20 minutes to cross the valley to the other side and back, General A can send messengers to the other side every 20 minutes until he receives the first courier confirmation from General B on the other side (he will no longer send messengers).

The above two strategies are a trade-off between speed and cost. Which one to use depends on which one is more suitable for the problem we encounter.

3. Why is the TCP three-way handshake [1] considered an engineering solution to the double generals problem?

There is a question on Zhihu: Why does TCP use three handshakes instead of two or four? [2] There are three answer angles.

①Why does TCP use three handshakes instead of two or four? - Answer by Punk Snowball Rabbit - Zhihu [3]

②(Why does TCP use three handshakes instead of two or four? - Che Xiaopang's answer - Zhihu [4]

③Why does TCP use three handshakes instead of two or four? - wuxinliulei's answer - Zhihu [5]

I hope everyone will read it carefully.

First we need to know:

The three-way handshake is to synchronize (syn) the sequence number (seq=m) in both directions. Synchronizing the sequence number requires two packets, one in each direction, so there are four packets in both directions. The second and third packets sent by one side can be merged together to form the last three packets.

But according to the double generals problem, who says that two packets back and forth can ensure successful synchronization?

In order to alleviate the double general problem, the TCP 3-way handshake adds a timeout retry mechanism. (Note: the retry is only done on the initiator of information synchronization)

The first packet: The SYN sent from A to B is lost and does not reach B.

A will periodically timeout and retransmit until it receives confirmation from B.

The second packet, the SYN+ACK sent to A, is lost and does not reach A.

B will periodically time out and retransmit until it receives confirmation from A.

The third packet: The ACK sent by A is lost on the way and does not reach B

After A sends ACK, it unilaterally believes that TCP is in Established state, while B obviously believes that TCP is in Active state.

a. Assuming that neither party has data to send at this time, B will periodically timeout and retransmit until it receives A's confirmation. After receiving A's confirmation, B's TCP connection will also be in the Established state, and packets can be sent in both directions.

b. Assuming that A has data to send at this time, B receives A's Data + ACK, and will naturally switch to the established state and accept A's Data.

c. Assuming B has data to send, but cannot send the data, it will periodically timeout and retransmit SYN + ACK until it receives A's confirmation and can then send the data.

• https://finematics.com/two-generals-problem/• https://www.bilibili.com/read/cv16604716

Summarize

This article documents the Two Generals Problem: For unreliable channels, countless confirmations cannot reach a 100% reliable consensus.

The TCP three-way handshake confirms the sequence numbers of packets in both directions and adds timeout retries, which is an engineering solution to the two generals' problem.

Reference Links

[1] TCP three-way handshake: https://blog.csdn.net/weixin_35942339/article/details/112733885

[2] Why is TCP a three-way handshake instead of two or four? : https://www.zhihu.com/question/24853633/answer/573627478

[3] Why does TCP use three handshakes instead of two or four? - Answer by Punk Snowball Rabbit - Zhihu: https://www.zhihu.com/question/24853633/answer/200721662

[4] (Why does TCP use three handshakes instead of two or four? - Che Xiaopang's answer - Zhihu: https://www.zhihu.com/question/24853633/answer/115173386

[5] Why is TCP a three-way handshake, rather than two or four? - wuxinliulei's answer - Zhihu: https://www.zhihu.com/question/24853633/answer/63668444