<p>Suppose we have two points, <code>A</code> and <code>B</code>, each point has its own clock.</p>

<p>We are able to send messages between <code>A</code> and <code>B</code>, the message takes some random delay to be delivered: 
$$min &lt; delay &lt; max,$$for each message the actual delay is unknown.</p>

<p>In this setup:</p>

<ul>
<li>Can we sync clock at this points perfectly?</li>
<li>Can we prove that it is impossible to sync perfectly?</li>
<li>Can we prove that it is impossible to sync this clock with a precision, which is better than some $f(min, max)$? (In other words, that after any sync process, this clock will still have difference at least $f(...)$)</li>
</ul>

<p><code>Precision</code> is the difference between this clock after actually syncing.</p>

CC BY-SA 3.0
2014-01-21T10:27:57.150Z
I asked the same question in physics, http://physics.stackexchange.com/questions/94488/synchronizing-time-between-two-points but I bet that was the wrong place.
Rustem Mustafin
CC BY-SA 3.0
2014-01-21T14:36:56.153Z
Is the delay fixed?
i.e. if A sends B a couple of messages, will the delay be the same?
R B
CC BY-SA 3.0
2014-01-21T20:08:43.387Z
@RB for each message the delay is random. Although, nothing forbids you to pack several data items in one message.
Rustem Mustafin
CC BY-SA 3.0
2014-01-21T21:19:41.880Z
What distribution do the random delays take? If it's from a fixed distribution and min,max are bounded (or, rather, the variance is bounded), A and B can keep sending timestamps back and forth (replying as soon as they get the message) to identify the average ping within a small error (via CLT), and then adjust the clocks as necessary based on the timestamps.
Yonatan N
CC BY-SA 3.0
2014-01-21T23:00:39.260Z
Time is relative. http://en.wikipedia.org/wiki/Twin_paradox In general you are screwed unless you can ensure that they keep their pings (speed of light distance) within a tight tolerance.
Chad Brewbaker
CC BY-SA 3.0
2014-01-22T03:12:34.940Z
@ChadBrewbaker I don't think the OP is interested into taking account a changing distribution of delays (as would happen if the distance between the objects changes) or clocks running at different rates (as would happen if they are moving at different velocities or in different gravitational potentials). However, I think OP should clarify if the clocks are known to run at the same rate and just need their current counters synched or if they need to figure out difference in rate.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-22T15:49:53.033Z
@ArtemKaznatcheev agreed. The fixed latency and bandwidth should be specified as constant parameters. I am a fan of  David Bader's $(\tau + \sigma m)$ notation http://www.cc.gatech.edu/~bader/COURSES/UNM/ece638-Fall2004/papers/HBJ98.pdf
Chad Brewbaker
CC BY-SA 3.0
2014-01-23T10:04:34.210Z
@ArtemKaznatcheev @ChadBrewbaker I thought, that was clear enough. The `delay` aka `latency` is random, within `(min, max)`. If it is simpler, you can treat `min` as time, required for light to travel between this points, and `max` as some delays in actual processing.
Rustem Mustafin
CC BY-SA 3.0
2014-01-23T10:13:10.750Z
@ArtemKaznatcheev @ChadBrewbaker Let's assume `delay` distribution is normal. Regarding clock rates, I'd say these are ideal clock, they just show different values initially, which also have fixed position. Regarding `bandwidth` let's say that it is unlimited, except that there must be some time between two messages.
Rustem Mustafin
CC BY-SA 3.0
2014-01-28T04:54:16.383Z
BTW Isn't this exactly the scenario NTP has to contend with?
Mark Hurd
<approximation-algorithms><optimization>
Sync time between two points
Rustem Mustafin
# Sync time between two points

(Asked by: username_0 on 2014-01-21)

Suppose we have two points, `A` and `B`, each point has its own clock.

We are able to send messages between `A` and `B`, the message takes some random delay to be delivered:
$$min < delay < max,$$for each message the actual delay is unknown.

In this setup:

* Can we sync clock at this points perfectly?
* Can we prove that it is impossible to sync perfectly?
* Can we prove that it is impossible to sync this clock with a precision, which is better than some $f(min, max)$? (In other words, that after any sync process, this clock will still have difference at least $f(...)$)

`Precision` is the difference between this clock after actually syncing.

**Tags:** approximation-algorithms, optimization
> **Comments:**
> **username_0**: I asked the same question in physics, http://physics.stackexchange.com/questions/94488/synchronizing-time-between-two-points but I bet that was the wrong place.  
> **username_1**: Is the delay fixed? i.e. if A sends B a couple of messages, will the delay be the same?  
> **username_0**: @RB for each message the delay is random. Although, nothing forbids you to pack several data items in one message.  
> **username_2**: What distribution do the random delays take? If it's from a fixed distribution and min,max are bounded (or, rather, the variance is bounded), A and B can keep sending timestamps back and forth (replying as soon as they get the message) to identify the average ping within a small error (via CLT), and then adjust the clocks as necessary based on the timestamps.  
> **username_3**: Time is relative. http://en.wikipedia.org/wiki/Twin_paradox In general you are screwed unless you can ensure that they keep their pings (speed of light distance) within a tight tolerance.  
> **username_4**: @ChadBrewbaker I don't think the OP is interested into taking account a changing distribution of delays (as would happen if the distance between the objects changes) or clocks running at different rates (as would happen if they are moving at different velocities or in different gravitational potentials). However, I think OP should clarify if the clocks are known to run at the same rate and just need their current counters synched or if they need to figure out difference in rate.  
> **username_3**: @ArtemKaznatcheev agreed. The fixed latency and bandwidth should be specified as constant parameters. I am a fan of  David Bader's $(\tau + \sigma m)$ notation http://www.cc.gatech.edu/~bader/COURSES/UNM/ece638-Fall2004/papers/HBJ98.pdf  
> **username_0**: @ArtemKaznatcheev @ChadBrewbaker I thought, that was clear enough. The `delay` aka `latency` is random, within `(min, max)`. If it is simpler, you can treat `min` as time, required for light to travel between this points, and `max` as some delays in actual processing.  
> **username_0**: @ArtemKaznatcheev @ChadBrewbaker Let's assume `delay` distribution is normal. Regarding clock rates, I'd say these are ideal clock, they just show different values initially, which also have fixed position. Regarding `bandwidth` let's say that it is unlimited, except that there must be some time between two messages.  
> **username_5**: BTW Isn't this exactly the scenario NTP has to contend with?  

---

## 0 answers

