Wednesday, December 30, 2009

Solution - Asymmetric Latency

The robots cannot figure out which room they are in, and they cannot distinguish the symmetric case from asymmetric cases. They can measure the round trip time, but never the one-way trip time.

Consider that the robots' actions are determined entirely by previously sent and received messages. Delay all messages by five seconds, and a robot's response will be five seconds later. Therefore, if we delay all incoming messages by five seconds, and accelerate all outgoing messages by five seconds, the net delay on the response is 0 seconds. Changing the symmetric case of 2s/2s to 1s/3s will have no effect on the robots' actions because the net delay is unchanged. They cannot tell the cases apart.

It is easier to understand this proof visually. Suppose the delays were equal. Then the propagation of messages might look like this:









Changing the one-way delay while holding the round-trip time constant is equivalent to sliding one of the timelines. The exact same case, except with all of the delay in one direction, looks like this:








Notice that, from the robots' perspective, both cases are equivalent. A2 arrives the same amount of time after A1, B2 arrives the same amount of time after B1, etc. In fact we can make one of the directions have a negative delay (go back in time) and the robots still can't tell the difference (the round trip time is still positive)!

No comments:

Post a Comment