Is there a solution to the Two Army Problem?

Ankita Katdare · 2011-05-10T05:19:52+00:00

While studying Transport Layer's 'releasing a connection' topic, I came across the famous 'Two Army Problem' Imagine that one army (say white army) is encamped in a valley. On both the surrounding hill sides is opposite army (say blue army). The white army is larger than either of the blue armies alone, but together they are larger than the white army. If either blue army attacks by itself , it will be defeated but if the blue armies attack simultaneously, they will be victorious. The blue armies want to synchronize their attacks. However, their only communication medium is to send messages on foot down into the valley, where they might be captured and the message is lost. The question is: Does a protocol exist that allows the blue armies to win? It's been proven that no such protocol exists that works. Any ideas?

Is there a solution to the Two Army Problem?

Ankita Katdare
@abrakadabra

Updated: Oct 25, 2024

Views: 2.7K

While studying Transport Layer's 'releasing a connection' topic, I came across the famous 'Two Army Problem'

Imagine that one army (say white army) is encamped in a valley. On both the surrounding hill sides is opposite army (say blue army). The white army is larger than either of the blue armies alone, but together they are larger than the white army.
If either blue army attacks by itself , it will be defeated but if the blue armies attack simultaneously, they will be victorious.

The blue armies want to synchronize their attacks. However, their only communication medium is to send messages on foot down into the valley, where they might be captured and the message is lost.
The question is: Does a protocol exist that allows the blue armies to win?

It's been proven that no such protocol exists that works. Any ideas?

0

Replies

Howdy guest!

Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.

Replies

PraveenKumar Purushothaman

Member • May 14, 2011

Couldn't understand this part!

If either blue army attacks by itself , it will be defeated but if the blue armies attack simultaneously, they will be victorious.
But in case of TCP Protocol, which lays in the Transport Layer, it should be synchronised in order to establish a communication right. So, the protocol is currently existing in TCP... What say?

Are you sure? This action cannot be undone.
Cancel
xheavenlyx

Member • May 14, 2011

If we look at it as a non-technical, real life challenge, then:

1. Smoke signals in Morse code.

2. Light signal using large reflectors made up of shields of 20 soldiers (god bless those guys...)

3. Fire at WILL!!

Are you sure? This action cannot be undone.
Cancel
MegaByte

Member • May 14, 2011

AbraKaDabra
If either blue army attacks by itself , it will be defeated but if the blue armies attack simultaneously, they will be victorious.

It should be:

If either of the blue army (any one of the blue army) attacks the white army, it will be defeated. But if both the blue armies attack simultaneously, they will be victorious.

Are you sure? This action cannot be undone.
Cancel
MegaByte

Member • May 14, 2011

I've read it somewhere that, in most of the protocols, there is the uncertainity of the last handshake message that is being sent. Thus, no protocol exists that allows proper communication in the Two Army problem.

Are you sure? This action cannot be undone.
Cancel
durga ch

Member • May 14, 2011

is there a solution to it?
If you do a netstat in your comp ( for windows), you can se variety of tcp connections , most of them will be in established state and few of them in transition states, incase the ack of ack is not recieved, the other party will never know their ack as recieved, thus never close the session. such connections will be in fin-wait mode

Are you sure? This action cannot be undone.
Cancel
PraveenKumar Purushothaman

Member • May 14, 2011

durga
is there a solution to it?
If you do a netstat in your comp ( for windows), you can se variety of tcp connections , most of them will be in established state and few of them in transition states, incase the ack of ack is not recieved, the other party will never know their ack as recieved, thus never close the session. such connections will be in fin-wait mode
They too have a limit. Acco. to the RFC of TCP connection, after a 60 second wait, it gets closed.

Are you sure? This action cannot be undone.
Cancel
vik001ind

Member • May 14, 2011

The blue armies want to synchronize their attacks. However, their only communication medium is to send messages on foot down into the valley, where they might be captured and the message is lost.
It's evident that there is no other form of communication other than sending a man.
let's assume left blue army is B1 & right one is B2. B1 sends a man(m1) to B2 & B2 sends a man (m2) back to B1 or vice versa for syncing the attack. The problem is that the man may be caught in the middle.
The winning probability depends on probability of both men not getting caught. Let's assume everyone in the blue army has the same probability of not getting caught ie. p[n], which is highly unlikely in real senario. Therefore winning probability depends on p[n]*p[n].

Their stategy should be to keep sending men till their strength is greater than white army & hope someone will reach back to them from B2. This is important because there is a very high probability of lossing if they don't sync their attack.
If the blue army is not aware of the strength white army, they should still keep sending men as they gonna lose either way.

Another strategy could be of non acknowledgement type. B1 sends a few men & hopes atleast one will reach b2 & make them aware of the attack time. The number of men send by b1 depends on the p[n]. Suppose, p[n]=1/5, then b1 should send atleast 5, but still it's possible that all of them are caught. For this strategy to work, blue army should know their p[n].

Blue army must stick to a stategy as there is very very high probability that they will lose if they don't follow any strategy.

That's all I can make out of this problem. 😀

Are you sure? This action cannot be undone.
Cancel
durga ch

Member • May 14, 2011

praveenscience
They too have a limit. Acco. to the RFC of TCP connection, after a 60 second wait, it gets closed.
yes,, so timeout i think can be considered as amitigation effort when we want to close the session, but incase A wants to start the session and the syc fails to reach B, and since B did not recieve any syc it wont ack and since B did not ack, A assumes it lost connection to B and doesnot do a syc -ack-ack. or am i getting this wrong?
but there is always that A can retry.

@ VIK: even i took time to understand that the above problem relates to TCP sessions, the problem statement kinda looks incomplete without the complete context.

Are you sure? This action cannot be undone.
Cancel