NTP; Berkeley vs Cristian

Network Time Protocol (NTP)

NTP is an Internet protocol (UDP port 123) that synchronises computer clocks to UTC over variable-delay networks.

• Servers are arranged in a hierarchy of strata: stratum 0 = reference clocks (GPS, atomic); stratum 1 = servers directly connected to them; stratum 2 gets time from stratum 1, and so on.
• A client talks to several servers and uses statistical filtering to select the best.
• Modes: multicast (LAN, low accuracy), procedure call (like Cristian's) and symmetric (peers, highest accuracy).
• In a message exchange with timestamps Ti−3 (request sent), Ti−2 (request received), Ti−1 (reply sent), Ti (reply received): delay d = (Ti − Ti−3) − (Ti−1 − Ti−2), offset o = ((Ti−2 − Ti−3) + (Ti−1 − Ti)) / 2. The best of the last eight pairs (smallest delay) is used.
• Reliable (many servers, tree reconfigures on failure), scalable and authenticated. Accuracy: milliseconds on the Internet, below 1 ms on LANs.

How Berkeley reduces the single-server problem of Cristian

Cristian's algorithm depends on one passive time server, which if it fails or has a wrong clock, stops synchronisation for all. The Berkeley algorithm (internal synchronisation) has no external time source:

1. A master (time daemon) is elected; it polls all slaves for their clock values.
2. Slaves reply; the master estimates each one's time using round-trip delay.
3. The master computes the average of all clocks (ignoring faulty ones that differ too much, and including its own).
4. The master sends each machine the adjustment (not an absolute time) needed, positive or negative, which avoids the transmission delay error. Clocks are slowed, not set back.
5. If the master fails, another machine is elected as master, so the service continues.

Thus failure of one node does not stop the system, and the averaging reduces the effect of a single bad clock.