Physical clock synchronisation


Physical Clock Synchronization: NTP

Motivation

In centralized systems, only one clock is present. A process can know the time by making a system call to the kernel. In distributed systems, there is no single global clock or common memory. Each processor has its own internal clock and its own local time. These clocks can drift seconds per day, leading to large errors over time. Since different clocks tick at different rates, they may not stay synchronized even if they start together. This creates problems for applications that require synchronized time.

For most distributed system applications, time is required in the following ways:

  • To know the time of day when an event happened on a specific machine.
  • To know the time interval between events that happened on different machines.
  • To know the relative ordering of events on different machines.

Without a common notion of time across machines, such queries cannot be answered. Clock synchronization is important for secure systems, fault diagnosis, recovery, scheduling, database systems, and real-world clock values.

Clock Synchronization

Clock synchronization means ensuring that distributed processors have a common notion of time. Since clock rates differ, clocks diverge over time. Therefore, synchronization must be done periodically to correct clock skew. Synchronization is done with respect to an accurate real-time standard such as UTC (Universal Coordinated Time). Clocks that must follow physical time and also synchronize with each other are called physical clocks.

Definitions and Terminology

  • Time: Time of a clock in machine p is given by Cp(t). For a perfect clock, Cp(t) = t.
  • Frequency: The rate at which a clock progresses. Frequency at time t of clock C is C′(t).
  • Offset: Difference between clock value and real time. Offset of clock Ca is Ca(t) – t. Offset of Ca relative to Cb at time t is Ca(t) – Cb(t).
  • Skew: Difference in frequencies of a clock and a perfect clock. Skew of Ca relative to Cb at time t is (Ca′(t) – Cb′(t)). If bounded by ρ, divergence is within (1 – ρ) to (1 + ρ).
  • Drift (rate): Second derivative of clock with respect to time. Drift of Ca relative to Cb at time t is (Ca′′(t) – Cb′′(t)).

Clock Inaccuracies

Physical clocks are synchronized to UTC. But due to inaccuracies, a clock works within its specification if the skew rate is within manufacturer limit ρ:

(1 – ρ) ≤ dC/dt ≤ (1 + ρ)

Behavior of Clocks

  • Fast Clock: dC/dt > 1
  • Perfect Clock: dC/dt = 1
  • Slow Clock: dC/dt < 1

Figure 3.5 shows how fast, slow, and perfect clocks behave with respect to UTC.




Offset Delay Estimation Method (NTP)

The Network Time Protocol (NTP) is widely used for synchronization on the Internet. It uses the Offset Delay Estimation method.

  • The NTP design follows a hierarchical structure of servers.
  • The root (primary server) synchronizes directly with UTC.
  • Secondary servers act as backups for the primary.
  • Clients form the lowest-level synchronization subnet.

Clock Offset and Delay Estimation

In practice, exact time on another node cannot be estimated due to variable network delays. To handle this, several trials are performed, and the trial with minimum delay is chosen.

In NTP, four timestamps are exchanged between peers A and B: T1, T2, T3, T4. Assuming both clocks are stable and run at the same speed:

Let a = T1 – T3 and b = T2 – T4.

If the differential delay (difference in delays A→B and B→A) is small, then:

  • Round-trip delay (δ) = a – b
  • Clock offset (θ) = (a + b)/2

Both peers calculate these values independently using one bidirectional message stream.




NTP Synchronization Protocol

Servers in symmetric mode exchange message pairs and maintain records of offset and delay.

Each peer stores pairs (Oi, Di):

  • Oi = offset
  • Di = delay

The offset corresponding to the minimum delay is chosen.

If A(t) is local clock of A and B(t) of B, then:

A(t) = B(t) + O

The eight most recent (Oi, Di) pairs are stored. Delay and offset are calculated as:

  • Offset Oi = (Ti–2 – Ti–3 + Ti–1 – Ti)/2
  • Delay Di = (Ti – Ti–3) – (Ti–1 – Ti–2)

The Oi with minimum Di is chosen to estimate O.