The Two Generals' Problem

PUBLISHED ON JUL 31, 2014 — MISC

The problem

Two nations, the Reds and the Blues, are entangled in a brutal century-long war. After a series of carefully staged tactical manoeuvres the Reds have managed to flank Azure, the capital city of the Blues. With a well-timed attack both halves of the Red army can collapse on the Blues and take Azure easily. However, Azure has a high enough Blue military presence that a solitary invading half of the Red army would be massacred.

The leader of one half of the Red army, General Crimson, is a seasoned battle strategist and fully recognises the importance of staging a coordinated attack. He pens a letter detailing the time of attack to his brother, General Scarlet, who commands the other half of the Red army. Due to the surrounding terrain the only way to deliver the message is to send a trooper in cognito through Azure. Of course, this is a dangerous task for the Red trooper and there is a chance that the message may be lost. General Crimson instructs Scarlet to return a confirmation letter in order to avoid a mixup in which Scarlet is oblivious to the prescribed attack time whilst Crimson sends his troops to their deaths. Unfortunately, this second messanger may also be intercepted so Crimson plans a confirmation of confirmation message… which may be intercepted as well. General Crimson thinks some more and frowns - no matter how many messengers he and his brother send there is no way to ensure that both halves of the army agree on attacking!

Thoughts

The Two Generals’ Problem is something I like to reflect upon every now and then. It is interesting due to its high significance in computer systems where networks have a tendency to fail and drop transmitted messages. Furthermore, the problem is proven to be unsolvable with 100% certainty. There is something enthralling, yet slightly unsettling, about a straightforward problem with no solution. Sure, engineers can devise protocols with high enough chances of success that any statistician would be satisfied. However, I am not a statistician and I would be rather anxious in General Crimson’s shoes as I sent my troops into battle with evan a small chance of being slaughtered.

TAGS: THEORY