Time Synchronization

Time Synchronization

In distributed systems, each node has its own physical clock that drifts over time. Time synchronization algorithms keep these clocks close enough to agree on ordering and deadlines.

Clock Skew and Drift

• Clock skew: The difference between two clocks at a given instant.
• Clock drift: The rate at which a clock deviates from real time (typically 10–100 ppm for quartz oscillators — that is 1–10 ms per 100 seconds).

Without synchronization, clocks diverge unboundedly, breaking log ordering, lease expiry, cache TTLs, and causality assumptions.

Cristian's Algorithm (1989)

A client asks a time server for the current time:

1. Client records t0 (local time before request).
2. Server replies with its time T_server.
3. Client records t1 (local time after response).
4. Client estimates round-trip time: RTT = t1 - t0.
5. Client sets its clock to: T_server + RTT / 2.

The RTT / 2 term estimates one-way network delay (assuming symmetric paths).

Client  ──── request (t0) ────▶  Server
        ◀── T_server reply ───  Server
Client records t1
New client time = T_server + (t1 - t0) / 2

Accuracy: ±RTT/2 in the best case. Outlier RTTs can be discarded.

Berkeley Algorithm (1989)

Unlike Cristian's (which uses an external time source), the Berkeley algorithm synchronizes clocks among peers with no authoritative server:

1. A coordinator polls all nodes for their clock values.
2. The coordinator computes the average of all times (including its own), discarding outliers.
3. The coordinator sends each node the offset (adjustment) needed to reach the average.
4. Each node adjusts its clock by the offset.

This does not give accurate real time — it gives agreement among nodes, which is often sufficient for internal coordination.

NTP (Network Time Protocol)

NTP is the internet standard (RFC 5905). It uses a hierarchy of strata:

• Stratum 0: Atomic clocks, GPS receivers (reference clocks).
• Stratum 1: Servers directly connected to stratum 0.
• Stratum 2: Servers synced to stratum 1, and so on.

NTP estimates offset and delay from four timestamps (similar to Cristian's but with more filtering and a hierarchical trust model). It achieves sub-millisecond accuracy on LANs and ~10 ms over the internet.

Your Task

Implement two functions:

1. cristian(t0, serverTime, t1) — returns the estimated synchronized time using Cristian's algorithm: serverTime + (t1 - t0) / 2.

2. berkeley(times) — takes an array of clock values (first element is the coordinator), computes the average, and returns an array of offsets each node must apply. Each offset is average - nodeTime, rounded to 2 decimal places.