Saturday, April 12, 2008

Almost sure colearning

In a prior entry we defined the act of colearning between agents A and B as a special mode of acquiring knowledge such that when some proposition φ is colearnt by A it follows that the fact "A knows φ" is colearnt by B, and viceversa. If A and B communicate through a reliable channel, i.e. they both know that each message from one to the other is guaranteed to get across, then implementing colearning is simple: when A gets to know φ, she just has to send a message to B informing of this fact.

If the channel is unreliable with probability 0 < P < 1 that each message is succesfully delivered, colearning cannot be achieved, but we can get almost sure colearning, i.e. colearning with probability one, with the only prerequisite that A and B behave in the following manner:

  1. Every message is sent over and over (with some arbitrary delay between sends) until an acknowledgement is received.
  2. An acknowledgement is always sent to every message received.
  3. The fact that A and B follow rules 1 and 2 is coknown by A and B.

So, we have turned an unreliable channel into an almost surely reliable channel where each message is delivered with probability one; this is not the same as a reliable channel, though.

Almost sure colearning is directly applicable to the two-army problem previously discussed: we can have the armies reach an agreement on when to make a joint attack with probability one. This is not in contradiction with the proved unsolvability of the original problem. In particular, almost sure colearning cannot be achieved in bounded time.

No comments :

Post a Comment