Cristian's algorithm

Clock synchronization

Clock synchronization is the process of making the clocks of the computers in a distributed system show the same time (or a time within a small bound). Each computer has its own crystal clock, and the clocks run at slightly different rates.

Need

• Time-stamped events (logs, transactions, file modification time) must be ordered correctly across machines; e.g. tools like make rebuild wrongly with inconsistent times.
• Distributed algorithms (mutual exclusion, deadlock detection, replication, security tickets with expiry) depend on a common time.
• Billing, auditing, scheduling and real-time control need agreed times.

Cristian's algorithm

It uses a time server (with a UTC receiver). A client asks for the time and corrects its clock using the reply, compensating for network delay.

 Client                         Time Server
   |---- request (at T0) -------->|
   |                              | reads time T_S
   |<--- reply (T_S) -------------|
   | (reply arrives at T1)        |

Steps:

1. Client records T0 and sends a request to the time server.
2. Server replies with its current time T_S.
3. Client records arrival time T1. Round-trip time = T1 − T0.
4. Assuming symmetric delay, the reply took (T1 − T0)/2, so the client sets its clock to T_new = T_S + (T1 − T0)/2.

Accuracy is ± ((T1 − T0)/2 − Tmin), where Tmin is the minimum one-way delay. Improvements: take several measurements and use the one with the smallest round trip; never set the clock backwards (slow it down gradually).

Example: T0 = 10:00:00.000, T1 = 10:00:00.020, T_S = 10:00:05.000. Client sets T_new = 10:00:05.000 + 0.010 = 10:00:05.010.

Limitation: the single time server is a single point of failure and a bottleneck.