Epistemics of the two-army problem

The so-called two-army problem is well known among students of computer networks: Two allied armies A and B are physically separated and must decide on a common time to make a joint attack, with the additional constraint that they can only communicate through an unreliable channel. Let's say A sends a message to B proposing to attack at 9:00 AM. If B receives the message it will send an acknowledegment back to A, but as the communication channel is faulty B cannot know for sure whether the acknowledgement is received, thus making the decision to attack at 9:00 a risky one in case A does not join. Both armies can send acknowledgements back and forth to increase their confidence that they have agreed to make the joint attack at 9:00 AM, but it can be easily proved that no amount of message exchange through the unreliable channel can guarantee 100% confidence --the key argument is that if there were a last message from one army to the other settling the agreement for good, the uncertainty on whether the message got through would render this allegedly definitive message inconclusive.

This puzzle is used to illustrate the limitations of unreliable communication channels, but as I see it the more fundamental limitation is not related to communication unreliability, but rather to the impossibility of acquiring common knowledge: Let us introduce the modal operators K_A and K_B stating that A and B respectively know some given fact. So, if φ is the statement "A proposes to attack at 9:00 AM", the successive, succesful exchanges between A and B will render the following statements true:

K_Bφ,
K_AK_Bφ,
K_BK_AK_Bφ,
K_AK_BK_AK_Bφ...

But in order for both armies to have complete confidence that they will make the joint attack at the stipulated time, we would need to establish an infinite amount of statements of the form:

(K_AK_B)ⁿφ and K_B(K_AK_B)ⁿφ, n = 0,1,2,...

The properties of epistemic logic imply that K_Aφ → K_AK_Aφ → K_AK_AK_Aφ → ..., which follows from the common-sensical fact that if somebody knows something, she knows that she knows it. But we don't have this sort of introspection capacity when two knowing agents are involved.

Suppose now that there were some special mode of acquiring knowledge of a certain proposition that we will call colearning, such that when φ is colearnt by A it follows that K_Aφ is colearnt by B, and viceversa. By recursion, B colearning φ implies the whole set of sentences (K_AK_B)ⁿφ and K_B(K_AK_B)ⁿφ described above.

Colearning is impossible in the presence of an unreliable communication channel. But we will see in a later entry that we can implement almost sure colearning, i.e. colearning with probability one.