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)!

Wednesday, December 23, 2009

Puzzle - Asymmetric Latency

Suppose two robots are placed in separate isolated rooms, called A and B. They can communicate, but the communication delay is not symmetric: it takes one second for a message to travel from room B to room A, but three seconds for a message to travel from room A to room B. The robots do not know which room they are in, and they do not have synchronized clocks. The only information they share is some preconceived plan/program for sending messages and responses.


Questions:
1) Can the robots figure out which rooms they are in?
2T) If so, could they figure out the exact values of the one way latencies?
2F) If not, could they at least distinguish cases where the latency is asymmetric from cases where the latency is equal both ways?