• Table of Contents

Clock Synchronization

Just like usual clocks, systems have a clock that tells time to applications running on the system.

• Centralized machines have just $1$ clock, but in the case of distributed systems each machine has its own clock.
• All these clocks might not be in sync and may drift over time. Hence the time will be dependent on which local clock is being checked.

Consider two hosts in a code development setup, which are out of sync by $2$ ticks.

Figure 5.1 Each machine has its own clock.

1. You make changes to a file on host 1 and save it. The local timestamp on host 1 is recorded.
2. On host 2, you initiate the compilation process for the modified file. However, due to the faster clock on host 2, its local timestamp might be later than the timestamp of the file edited on host1.
3. The compilation process checks timestamps to determine whether the file needs recompilation. In this case, it may incorrectly perceive that the file on host 1 is older than the compilation output on host 2, leading to the assumption that the file has not changed.
4. As a result, the compiler skips recompiling the file, assuming it's up-to-date, despite the recent changes made on host 1.

In computer systems, clock skew refers to the difference in time readings between the clocks of different machines. This skew is mainly attributed to the inherent variations in the frequencies of crystals used in the physical clocks of computers.

• Physical Clocks: Computers utilize crystals that oscillate at a constant frequency to maintain time. However, due to slight variations, these crystals may run at different frequencies across different computers. The resulting time difference is known as clock skew.
• Software Clocks: To implement a software clock (denoted as $C$), a counter is employed. The hardware clock generates interrupts at a frequency denoted as $f$ times per second. Each interrupt event increments the software clock counter.

Now, the question of how do we synchronize them with real-world clocks, and how do we synchronize the clocks with each other?

Clock Synchronization Algorithms

The foundation for maintaining a globally consistent time in distributed systems is the Coordinated Universal Time (UTC). Represented as $t$, $C_p(t)$ denotes the value of the software clock counter on machine $p$ at time $t$.

• Internal synchronization: The primary objective of clock synchronization algorithms is to ensure that the deviation between the clocks of any two machines within the distributed system remains within a specified bound, known as precision ($\pi$).

  $$ \forall t, \forall p, q : |C_p(t) - C_q(t)| \leq \pi $$

  It's crucial to note that precision specifically addresses the deviation between clocks of machines within the distributed system.

• External synchronization: When considering an external reference point, such as UTC, the focus shifts to accuracy. The goal is to limit the difference between the clock of a particular machine and the actual time to a predefined value ($\alpha$).

  $$ \forall t, \forall p : |C_p(t) - t| \leq \alpha $$