Cristian's algorithm

Cristian's Algorithm is a method for clock synchronisation which can be used in many fields of distributive computer science. 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

Christian'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 returning 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).