> For the complete documentation index, see [llms.txt](https://ret2basic.gitbook.io/ctfnote/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ret2basic.gitbook.io/ctfnote/computer-science/distributed-systems/coordination/clock-synchronization.md).

# 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**