Two Generals problem

by Dmitry Kirsanov 27. July 2020 08:44

There is a logical problem, a thought experiment for emulating the communication over an unreliable link, called “the Two Generals’ Problem”. In case if, like most people, you never heard of it, here is the definition:

Two armies, each led by a different general, are preparing to attack a fortified city. The armies are encamped near the city, each in its own valley. A third valley separates the two hills, and the only way for the two generals to communicate is by sending messengers through the valley. Unfortunately, the valley is occupied by the city's defenders and there's a chance that any given messenger sent through the valley will be captured.

While the two generals have agreed that they will attack, they haven't agreed upon a time for attack. It is required that the two generals have their armies attack the city at the same time in order to succeed, else the lone attacker army will die trying. They must thus communicate with each other to decide on a time to attack and to agree to attack at that time, and each general must know that the other general knows that they have agreed to the attack plan. Because acknowledgement of message receipt can be lost as easily as the original message, a potentially infinite series of messages is required to come to consensus.

The thought experiment involves considering how they might go about coming to consensus. In its simplest form one general is known to be the leader, decides on the time of attack, and must communicate this time to the other general. The problem is to come up with algorithms that the generals can use, including sending messages and processing received messages, that can allow them to correctly conclude:

Yes, we will both attack at the agreed-upon time.

Allowing that it is quite simple for the generals to come to an agreement on the time to attack (i.e. one successful message with a successful acknowledgement), the subtlety of the Two Generals' Problem is in the impossibility of designing algorithms for the generals to use to safely agree to the above statement.

It’s even called a “paradox” for “inability to find a logical solution” to this problem. Because the proposed solution is to send confirmation for confirmation, and messenger could disappear.

If so many people are saying, that there is no solution, then perhaps there isn’t one, right?

A programmer’s approach

By definition, generals should agree upon attack, the agreement process starts at the evening and should conclude by morning. That’s around 10-12 hours. Let every general send one messenger every hour, with or without message. Each messenger you send to other party, informs other party about the last message you received, and when.

Let’s imagine, that general Alice decides the time has come. She sends message to general Bob. If messenger is lost, her next messenger should deliver the same message. Meanwhile messengers from Bob report, that no message was received.

Eventually, message passes through, and now Bob is sending message to Alice, that he agrees to attack, while messengers from Alice still sending her proposal for attack. Now, that a proposal was received, Bob increases the rate, at which he is sending messengers, let’s say – every 30 minutes. If Alice won’t receive any messenger from Bob for 3 hours, she assumes that her message is lost, and no attack is happening. She continues to send her messengers, and they are bringing the message that messengers from Bob were not received, and attack is postponed. Either due to the recall message, or due to lack of messengers in pre-defined time, Bob will know that attack won’t happen.

Once Alice receives the messenger from Bob, she switches to faster messaging mode too. In that mode, if they don’t get 4 messengers in a row, the plan is cancelled.

So, Alice sent Bob a message, he replied, she got his reply, and now she needs to let him know that answer is received and attack will happen. Well, it’s automatic – her messengers are going every 30 minutes and they are bringing information about the last message received by Bob, and vice versa. In 2 cycles they both will know, that they agreed to attack.

The final countdown

When Bob sees, that his reply was received, he is sending Alice a messenger with a number. Let’s say – “1”. She is supposed to send him “2”. The countdown is not important, it only means that we finalised the agreement on attack. At this stage we can lose messengers, but it won’t affect the outcome.

A two secrets approach

When Bob gets the call for attack from Alice, he is sending her his approval with first secret attached. She is supposed to start sending him second secret as reply. Again, they are flooding each other with messengers, so if Bob still receives the call for attack, he is sending the same reply with first secret.

Once Bob receives the second secret, his messengers start to carry that same second secret. When all messengers are carrying the second secret, both parties know they are in agreement.

Tags:

Other

blog comments powered by Disqus

Month List