Friday, February 26, 2010

A probabilistic solution to the Two Generals problem

Here is a probabilistic solution to the two General's problem; it gives a high probability of succcess if the number of messages(messengers) is kept high.

The two General's problem is a problem of synchronization between two army Generals. They have surrounded an enemy
army that is more powerful than any one of the two armies. But together the two armies outnumber the enemy and can win. The problem is that the two Generals are far enough from each other and can't communicate with each other except by sending messengers. The messengers have to move through enemy line. The messengers can either get caught or reach the other General with a message.How would the army Generals agree on a time to attack? If they don't synchronize their attack, the enemy will win. The receiver General has to send an acknowledgment back to the first General now. The acknowledgment has to be sent through a messenger. The messenger again has a possibility of getting caught by the enemy. To acknowledge the receipt of acknowledgment, a messenger has to be sent again. Thus, the cycle of acknowledgments will continue...

Let's make some assumptions before discussing a solution to this problem:


A1- Each messenger has 50% chance of reaching the other General with the message.
A2- We will expect a 99.999 % chance of agreement between the Generals as sufficient enough.
A3- Each General sends an equal number of messengers.

Now, the chance of a messenger reaching the other General is 50%; it means the chance of failure is also 50%. If a General sends N messengers, the probability that none of them will reach the other General is (0.5)^N. So, the probability that at least one of the messengers will reach the other General is 1-(0.5)^N.

So, the probability that at least one messenger from each General will reach the other General is (1 - (0.5)^N)^2. When at least one messenger from a General reaches the other General with a time to attack, and an acknowledge from the other General reach the first one the message+acknowledgment is complete and there is an agreement.

We are taking the probability of 99.999% as success.
So, (1-(0.5)^N)^2 > 0.99999
or, (1-(0.5)^N) > 0.999995 (thanks to the calculator that is present in Google search, "square root of .99999" and search)
or, 0.5^N > 0.000005
or, N = 17

So, if a General sends 17 messengers one after the other with a message, and the other General replies with 17 messengers with acknowledgment, we have a greater than 99.999% probability of an agreement on the time to attack. Increasing the number of messengers increase this probability even more.


Website Designing and Developm said...

I appreciate for post. I was looking for similar one. Can you update more details at link



Aasha said...

Really nice and definitely it will be useful for many people. Kindly keep update like this.

Email Marketing Chennai

Abiya Carol said...

This is an awesome post.Really very informative and creative contents. These concept is a good way to enhance the knowledge.I like it and help me to development very well.Thank you for this brief explanation and very nice information.Well, got a good knowledge.

Branding Services in Chennai

Harish Raju said...

This blog is having a wonderful talk. The technology are discussed and provide a great knowledge toall. This helps to learn more details about technology. All this details are important for this technology. Thank you for this blog.
Digital Marketing Company

Saki R said...

Expected and valid points are included in you blog.. I really liked and I got some clear ideas for improve my thoughts from well defined content... keep updating more for us... thanks for shared useful blog..
Java Training in Chennai

Shalini said...

Superb. I really enjoyed very much with this article here. Really it is an amazing article I had ever read. I hope it will help a lot for all. Thank you so much for this amazing posts and please keep update like this excellent article.thank you for sharing such a great blog with us. expecting for your.
Digital Marketing Company in India