The following example will show that common knowledge can never be achieved when the medium of communication is uncertain. The Byzantine
Generals problem, also called the coordinated attack problem was first introduced by Gray [2].
This problem concerns two Byzantine Generals, each in command of a division of an army. They want to attack a common enemy, located
in between of the two divisions. They can only win the battle if the two divisions attack the enemy simultaneously. If only one
division attacks, it will be defeated. The generals want to coordinate their attack in order to win, hence the name coordinated
attack problem. The only way in which the generals can communicate with eachother is by means of messengers who have to pass
the enemy in order to get to the other side. These messengers can be caught by the enemy or get lost on their way, so the medium of
communication is uncertain. We will see what the consequences of this are shortly.
Suppose general A sends a message to general B that states: "Attack Friday at 12:00pm", and suppose general B actually receives this message.
General A does not know that general B has received the message, so general B sends back the message: "Acknowledged: Attack Friday at 12:00 pm".
But now general B does not know if his acknowledgement is received by general A, so he (general A) sends an acknowledgement of the
acknowledgement back to general B. This sending and receiving can continue infinitely.
At all times, there is not enough information to start attacking, because both generals do not want to risk attacking
alone. Yemini and Cohen [3] proved by induction on the number of messages, that the generals will never attack no matter how many
succesful messages are being received.
This can be seen in the applet below. General A starts by sending a message to general B. If the messenger gets caught, and it takes him
too long for a return message, he sends the message again. Once the message is received by general B, he will send an acknowledgement
back to general A. This process continues infinately. Real common knowledge is never achieved.
Halpern and Moses [4] showed that there is a relation between common knowledge and the coordinated attack problem. They came up with two
different theorems regarding the Byzantine Generals problem:
A correct protocol for the coordinated attack problem must have the
property that whenever the generals attack, it is common knowledge that they are attacking.
Any correct protocol for the coordinated attack problem guarantees
that neither general ever attacks.
The first theorem says, that the generals can only attack if there is common knowledge about the attack. The second theorem
states that the generals will never attack, due to the fact that common knowledge is never achieved.
So the problem is clear now. The generals can wait as long as they want, but with this form of uncertain communication, an attack will
never take place. First we take a look at another example about two agents communicating with eachother.