Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This is a puzzle about measuring network latency that I created. I believe the solution is that it's impossible, but friends disagree. I'm looking for convincing explanations either way. (Though it is posed as a puzzle I think it fits on this web site because of its applicability to the design and experience of communication protocols such as in online games, not to mention NTP.)

Suppose two robots are in two rooms, connected by a network with differing one-way latencies as shown in the graphic below. When robot A sends a message to robot B it takes 3 seconds for it to arrive, but when robot B sends a message to robot A it takes 1 second to arrive. The latencies never vary.

The robots are identical and do not have a shared clock, though they can measure the passage of time (e.g. they have stop watches). They do not know which of them is robot A (whose messages are delayed 3s) and which is robot B (whose messages are delayed by 1s).

A protocol to discover the round trip time is 'when receiving TICK send TOCK, start watch, send TICK, await TOCK, stop watch, record time difference (4s)'.

Is there a protocol to determine the one way trip delays? Can the robots discover which of them has the longer message sending delay?

Two robots one asymmetric network

share|improve this question
5  
See Clock synchronization in a network with asymmetric delays (which asks for something doable with typical Internet infrastructure). I think from what we saw when discussing wrong answers to that question the answer to your question is that it's impossible. –  Gilles Mar 21 '12 at 13:14
    
Should we merge the questions, or are they different enough in target to keep separate? –  Strilanc Mar 21 '12 at 13:48
    
No, they are different questions. Your question establishes that it's impossible in a two-machine setting with just message passing. I'm hoping for solutions based on, say, latency information being available for some intermediate links on the route between the client and the server and having some way to propagate this information to the client. –  Gilles Mar 21 '12 at 13:57
3  
If there were a way to do this, Einstein's theory of relativity wouldn't work, since it depends on the fact that two observers who are space-like separated and have unknown one-way latencies cannot agree on a proper time. –  Peter Shor Mar 22 '12 at 15:07
    
NTP does indeed allow/implement measuring this differential delay based on machines sending each other their time & not merely tracking send/receipt time of their own msgs but also the other servers via msg contents, see answer on gilles question –  vzn Oct 1 '12 at 21:53

3 Answers 3

up vote 4 down vote accepted

The following diagram, from a blog post I wrote, is a visual proof that it's impossible:

Sliding the clock skew exactly offset by latency asymmetry

Notice how the packet arrival times on each side stay the same, even as the one-way latencies change (and even become negative!). Those are the only things a protocol could be based on, but they end up the same! Asymmetry in the one-way latencies looks exactly like initial clock skew, and since we don't know the initial clock skew we can't figure out the one-way latencies.

More formally, you can't solve for edge lengths when given only the lengths of the cycles. The cycle basis has $n-1$ degrees of freedom, corresponding to $n-1$ unknown clock skews relative to one of the participants. You can always hide the one-way latencies, even when there are many participants:

Sea sickness

If you're not so visually inclined, I have another intuitive argument. Imagine a time portal to a hundred years in the future. As you chat across it to someone on the other side, you realize the conversation is totally normal despite the hundred year asymmetry in one-way delays. Any observable effect would have been obvious on that scale!

share|improve this answer

I think it is impossible to figure out one-way latency just by comparing stopwatches.

$A$ sends $B$ his clock $C_{A1}$, let's say its value is 5.
$B$ acknowledges the message at time $C_{B1}=1$
$A$ sends his clock again, $C_{A2}=9$ (initial + round-trip latency).
$B$ receives at time $C_{B2}=5$.
And so on. Neither $A$ or $B$ can figure out when the other robot received a message with respect to their watches.

Maybe if you make it a bounty question someone will crack it. Until then, kudos.

share|improve this answer

Nice, diagram. Even if the robot were to send the initial tick over and over again at a certain rate I don't think it would be possible to determine which robot had a slower delay with just stop watches and no other communication between the two robots. All you would be able to get is network delay plus rate at which the machine is sending it.

Now if you added to the message the time the other robot send the message to the following message that would be a completely different scenario.

share|improve this answer
1  
The robots are allowed to include information in the messages. That includes the time the other robot send the message, except keep in mind that they don't have a shared clock so it would have to be stopwatch time. –  Strilanc Mar 21 '12 at 13:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.