The Byzantine Generals' Problem

Imagine a time during the dark ages, where a pirate ship is under attack. There are 200 pirates aboard the pirate ship surrounded by six army ships of 50 warriors each, who've anchored, surrounding the pirate ship. Each army ship is commanded by a captain. The 300 warriors can easily overpower the 200 pirates aboard the pirate ship. However, if they don't all attack simultaneously, there is a very real risk that the warriors will be outnumbered by the pirates and they'll go on to lose the battle.

Figure 1.2: Pirate ship (200) surrounded by arm ship (50)

So, how can the captains all agree on the same time to attack the pirate ship? These days, we'd simply need a quick group video-conference call, and the captains would have to agree to attack at 22:00 hours (10 PM).

However, back in the dark ages, things were a little more complicated:

• The 22:00 attack message could only be passed on by a sailor on a small boat. He has to sail around each army ship, visiting each captain in turn to confirm.
• Any captain may be a traitor and in league with the pirates in the pirate ship.

Losing strategy

Captain 1 decides to attack at 22:00. He sends his sailor out with the message (22:00 attack) to deliver to Captain 2. Upon arrival, Captain 2 reads the message, notes the time of the attack, and sends a message that also says 22:00 attack. He sends the sailor on to share the message with Captain 3. However, we have a problem. Captain 3 is a traitor. He wants the attack to fail. So, when he gets the message, he rips it up and replaces it with a new message that says 21:00 attack (9 PM). The sailor continues unaware. Captain 4 now receives a message saying 21:00 attack. He notes the time, signs the message saying 21:00 attack and sends this on to Captain 5, who then sends the same message to Captain 6. Now, the message has gone around everyone, but we have a problem. The dishonest captain has disrupted the result. We now have three captains (4, 5, and 6) with 150 warriors attacking the pirate ship at 21:00. Expecting others to join them, they instead get outnumbered and overpowered by the 200 pirates. The victorious pirates now stream out of the pirate ship and join forces with the treacherous Captain 3. Suddenly, the two remaining captains (1 and 2) have only 100 warriors and find themselves fighting 200 pirates plus 50 traitors. Unfortunately, the pirates and traitors win.

Winning strategy

Captain 1 wants to send the same message (attack at 22:00). However, this time, there are two new rules he must obey:

• He must spend 10 minutes preparing any new message for it to be valid
• He must include the history of every previous message in every new message

So, let's see what happens this time. As before, Captain 1 sends the message (22:00 attack) with the sailor on the boat. This time, however, it is different for Captain 2, because he knows two things for certain:

• The message must have taken 10 minutes to prepare
• There are no previous messages, so it must be the truth (even if Captain 1 is a traitor and put in the wrong time, it doesn't matter; if the majority of captains followed this suggestion and went with a 22:00 attack time, they would still outnumber those in the pirate ship and win the battle)

So, now it is time for Captain 2 to send a message. As required, he spends 10 minutes preparing the new message and he embeds Captain 1's message into his own. The sailor then sets off with this message (now in fact, it is two messages chained together as the second has the first embedded within it). Now it gets to Captain 3.

Remember, he's the traitor. So, what does he do? Last time, he changed the message to 21:00 attack so that captains 4, 5, and 6 would attack early and get overpowered. Now, however, he can't because, under the new rules, he has only 10 minutes to prepare a message for Captain 4. He has two options:

1. Cheat by changing the message to 21:00 attack. To do this, he needs to (a) spend 10 minutes creating his message and then (b) spend an extra 2 x 10 minutes working to create replacement 21:00 attack messages from Captains 1 and 2 to embed these into his message and carry out this 30 minutes of work within the next 10 minutes to avoid the other captains knowing that he's a traitor.
2. Admit defeat and prepare the 22:00 attack message during those 10 minutes.

In other words, every captain has got no more than 10 minutes to provide the next captain with something that would take more than 10 minutes to fake if they were trying to be dishonest. If they can't deliver it within 10 minutes, everyone knows they're dishonest and ignores them, rendering their attempts to mislead others useless.