TWO MEN ARMY PROBLEM

May 3, 2012 · Filed under computer science, IT SCHOOLS, Uncategorized · Tagged solution for two men army problem, TWO ARMY PROBLEM, two men army problem in networking, UNRELIABLE NETWORK

The Two Army Problem

I am reading a book on networking.  Computer Networks, Tanenbaum, 5/E.  One of the networking issues it is discussing is how to bring down a synchronous connection.  A synchronous disconnect is one where both the sender and receiver agree to terminate.  I have run into this exact same issue under a different guise in the past and did not know how to epitomize the core issue.  This is an issue at the heart of many acknowledged services.  Here is the problem in a nutshell as explained in the two army problem.Suppose there is a valley surrounded by two hills.  On one hill is Black army 1.  On the second hill is Black army 2.  In the valley is the Blue army.  Now the Blue army is larger then either of the individual Black army’s, but together the Black army is larger then the Blue.  If either Black army attacks Blue independently they would lose, but together they would win.  The problem for Black army 1 commander is to communicate a coordinated attack time to Black army 2.  But Black 1 needs to be SURE that Black 2 got the message or he would be delinquent in his duties and be stripped of command if Black 1 attacked alone.  So Black 1 commander sends a man though the Blue valley with this message, “We attack at dawn, acknowledge you received this message.”  Black 2 commander gets this message and sends a man with a message saying “We are with you and attack at dawn.”  Sending the courier back and forth is similar to an unreliable network because the courier could be caught or shot.Now there is a problem.  A BIG problem.  How does Black commander 2 know the acknowledgment got through?  If the acknowledgement didn’t get through then Black commander 2 would be attacking alone, since Black commander 1 did not get the acknowledgment and would not attack.  Black commander 2 can ask for an acknowledgment that the acknowledgment got through, but then we are back at the same problem on the other side! Think about it.  Black 2 asks for the ack to the ack.  Black 1 sends it.  How does Black 1 now know the ack to the ack got through?  If it didn’t Black 2 will not attack now. The courier going back and forth across the Blue army turf is like a noisy or unreliable network.  We are trying to make the network reliable by adding acknowledgments to the messages. That last asknowledgement is the critical message. This is an interesting problem!  There does not seem to be a clean solution presented that is 100% reliable, but there are workable solutions for particular applications.