Introduction
 
Ann & Bob Example
Byzantine Generals
Alice & Bob Example
 
Common Knowledge
ε-Common Knowledge
Eventual Common Knowledge
 
Conclusion
References

The Alice & Bob Example

Consider the following example. Alice and Bob are both agents that communicate over a channel that always delivers messages. No messages get lost on their way. Alice and Bob both know that this is the case, more strongly: it is common knowledge that the communication medium is reliable. The only thing that is somewhat uncertain is the delivery time of the message. It is commonly known that messages from Alice to Bob or vice versa arrive at ε time units.
 
But how do Alice and Bob make sure that they attain common knowledge about some fact. If ε=0, Alice and Bob attain common knowledge the moment the message is sent, but it always takes time to transfer a message. Suppose Alice sends Bob a message δ that does not specify the sending time. Bob does not know initially that the message came from Alice. We can assume that when Bob gets the message from Alice, he knows that it came from her. The state of knowledge of Alice and Bob can be described as follows:
 

  • Let S(δ) mean that Alice has sent message δ.
  • After ε time units, KAKB(S(δ)) holds.
  • Let (KAKB)KS(δ) mean S(δ) for k = 0.
  • Let KAKB(KAKB)K-1S(δ) for k>0
  • Then (KAKB)KS(δ) holds after kε time units, but not before then!

This means that common knowledge is never attained. It does not matter how large ε is, it might be a year or a microsecond, Alice and Bob will never attain common knowledge that the message was sent!
 
The uncertainty about the sending time can be removed if both Alice and Bob use the same clock, and instead of only sending the message δ, Alice also sends the time at which the message was sent with the message. In this way, the message always arrives at maximally m+ε time units. Because Alice and Bob both use the same clock, it is common knowledge that at time m+ε, it is m+ε. Thus at that moment in time, the fact that Alice sent message delta; to Bob is common knowledge.
 
What is the difference between these two examples? The only thing that has changed is to remove the sending time uncertainty. This is actually the bottleneck when trying to attain common knowledge. When a fact δ is common knowledge, everybody must know that it is common knowledge. It is impossible for Alice to know that δ is common knowledge and for Bob not. This means that the transition of a fact becoming common knowledge must involve a simultaneous event. All relevant agents must change their state of knowledge at the same time. This is what happens in the second example, due to the use of the same clock by the two agents.

<< Back || Next >>