Clock Synchronization

Motivation

• Clock synchronization is naturally related to time, although it may not be necessary to have an accurate account of the real time.

• It may be sufficient that every node in a distributed systems agrees on a current time.

• For running make it is adequate that two nodes agree that input.o is outdated by a new version of input.c, for example.

• In this case, keep tracking of each other's events is what matters.

Physical Clock

• Nearly all computers have a circuit for keeping track of time.

• All processes on the same computer use the same clock.

• Across multiple computers, clock skew happens.

Network Time Protocol (NTP)

• Let clients contact a time server.

• The problem is that when contacting the server, message delays will have outdated the report time.

• The trick is to find a good estimation for these delays:

  • Step 1: A sends a request to B, timestamped with T1

  • Step 2: B records the time of receipt T2

  • Step 3: B returns a response timestamped with T3, piggybacking T2

  • Step 4: A records the time of the response's arrival, T4

    • If $\theta < 0$, A's clock is faster than B (the time server)

    • A can slow down its clock by advancing less time every clock tick

  • A can estimate its offset relative to B as:

$$\theta = \frac{(T2 - T1) + (T3 - T4)}{2}$$

The Berkeley Algorithm

• The time server actively coordinates the clocks across the whole system.

• This is useful when there is no accurate clock in the system.

• For many purposes, it is sufficient for all computers to agree on the same time, not necessarily the real time.

• The time daemon computes the average and tells each machine how to adjust its clock.

  • Suppose the client clock reads 5:30 and the server clock reads 5:20, then both the client and the server will be set to 5:25