What is Clock Synchronization?

Clock Synchronization refers to syncing the time displayed by any two given clocks, such that either both the clocks display the exact same time at the exact same moment, and this remains constant over the passage of time, or both clocks show time with a difference that remains constant over the passage of time, such as if clock A is ahead by 6 hours as compared to clock B, then clock A should remain ahead by 6 hours as compared to clock B at any given point in time.

Ideally, all clocks should be in perfect sync. However, realistically this is difficult to achieve.

Important terminology

There is some terminology regarding clock synchronization that is worth noting:

• Skew: The difference between the synced times between two clocks at any given moment. For example, if two clocks that should display the same time have a 10-second difference in their displayed time, then the skew between the two clocks is of 10 seconds

• Drift rate: The rate at which a given clock may drift from an ideal clock.
  For example, ordinary quartz clocks normally drift by 1 second in 11–12 days.

To address clock synchronization issues, multiple algorithms have been devised that help attain clock synchronization as accurately as possible. Some of these algorithms are:

• Cristian's algorithm

• Berkeley's algorithm

• Network Time Protocol (NTP)

Cristian's algorithm

Cristian's algorithm is based on two assumptions:

• There is at least one clock that displays accurate time and can be utilized by other clocks to correct their time.

• The request time and the response time in a round trip will always be constant and thus can be used to estimate the delay time.

Note: Round Trip refers to the combined trip of a client's request and the server's response. Round Trip Time refers to the time taken by a Round Trip.

Let's resume our example of a distributed system containing a server and multiple clients, and assume our server has the correct time which the clients will request to determine their own time.

In Cristian's algorithm, four different times T1, T2, T3, and T4 are noted as the client sends a request to the server, the server processes the request and sends a response, and the client receives the response.

We have the following:

request time + response time = $(T4 - T1) - (T3 - T2)$

Assuming request time ≈ response time, we can denote $2Tr$ = request time + response time as,

$2Tr = (T4 - T1) - (T3 - T2)$

The client can set the time $T4 = T3 = 0.5Tr$

Berkeley's algorithm

Berkeley's algorithm builds upon Cristian's algorithm, however, it does not assume that there is any particular clock that is accurate. It instead utilizes all available clocks to arrive at a consensus.

Given $n$ nodes containing clocks that need to be synchronized, one node is appointed the leader while the rest are deemed the followers.

The leader node periodically pings all followers nodes and attains their times using Cristian's algorithm. Once all the times are attained, the leader node uses them (and its own time) to calculate the average time difference. The leader node then updates its own time using the calculated time difference and propagates the updated time over the network. Upon receiving the propagated time, the follower nodes then update their own times as well.

Network Time Protocol (NTP)

NTP is a protocol that is based on a hierarchical structure, consisting of multiple layers of nodes. Each layer in the protocol is referred to as a Stratum and is assigned a number $n$ ranging between $0$ to $15$. Clocks in the uppermost Stratum, Stratum 0, are the most accurate. The accuracy of the clocks decreases as the value of n increases.

Stratum 0 consists of highly precise clocks such as atomic clockshighly precise clocks that set their time by monitoring the resonant frequency of atoms, GPS, and radio clocks. These are directly connected to primary time servers in Stratum 1. Each Stratum n requests the Stratum n-1 above it for time, such as Stratum 2 clocks sending a request to Stratum 1 clocks. Clocks in the same Stratum may also coordinate with each other to further increase their accuracy.

Suppose Clock A in Stratum n is setting its time for the first time. Clock A would initiate a time request with Clock B in Stratum n-1. Six exchanges would take place between the two clocks over a period of 5 to 10 minutes. These would then be utilized by Clock A to set its initial time. Once the initial time would be set, Clock A would then update its time every 10 minutes by having an exchange with any clock in Stratum n-1.

A much stricter version of the NPT is known as the Simple Network Time Protocol (SNTP), which restricts peer-to-peer communication. Nodes are restricted to using the upper Stratum for synchronization purposes only.