Cristian's algorithm

Cristian's Algorithm is a method for clock synchronisation which can be used in many fields of distributive computer science but is primarily used in low-latency intranets. Cristian observed that this simple algorithm is probabilistic, in that it only achieves synchronisation if the round-trip time (RTT) of the request is short compared to required accuracy. It also suffers in implementations using a single server, making it unsuitable for many distributive applications where redundancy may be crucial.

The algorithm

Cristian's Algorithm works between a process P, and a time server S — connected to a source of UTC (Coordinated Universal Time). Put simply:

1. P requests the time from S
2. After receiving the request from P, S prepares a response and appends the time T, from its own clock at the last possible moment before dispatch.
3. P then sets its time to be T + RTT/2

It is important to note that the time is attached at the last possible moment before being returned to P. This is to eliminate inaccuracies caused by network delay.

P needs to record the Round Trip Time (RTT) of the request it made to S so that it can set its clock to T + RTT/2. This method assumes that the RTT is split equally between both request and response, which may not always be the case but is a reasonable assumption on a LAN connection.

Further accuracy can be gained by making multiple requests to S and using the response with the shortest RTT. We can estimate the accuracy of the system by taking RTT/2 from the fastest response as a value we call min. The earliest point at which S could have placed the time T was min after P sent its request. Therefore the time at S when the message is received by P is in the range (T + min) to (T + RTT - min). The width of this range is (RTT - 2*min). This gives an accuracy of (RTT/2 - min).