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.
3. P then sets its time to be T + RTT/2

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 as follows. Let min be the minimum time to transmit a message one-way. 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).

See also

• Allan variance
  Allan variance
  The Allan variance , also known as two-sample variance, is a measure of frequency stability in clocks, oscillators and amplifiers. It is named after David W. Allan. It is expressed mathematically as\sigma_y^2. \,...
  
  
• Clock synchronization
  Clock synchronization
  Clock synchronization is a problem from computer science and engineering which deals with the idea that internal clocks of several computers may differ. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift, caused by clocks counting time at...
  
  
• International Atomic Time
  International Atomic Time
  International Atomic Time is a high-precision atomic coordinate time standard based on the notional passage of proper time on Earth's geoid...
  
  
• ntpd
  Ntpd
  The Network Time Protocol daemon is an operating system daemon program that maintains the system time in synchronization with time servers using the Network Time Protocol .-Description:...
  
  , OpenNTPD
  OpenNTPD
  OpenNTPD is a Unix system daemon implementing the Network Time Protocol to synchronize the local clock of a computer system with remote NTP servers. It is also able to act as an NTP server to NTP-compatible clients....
  
   and Ntpdate
  Ntpdate
  ntpdate is a computer program used to synchronize and set computers' date and time by polling the Network Time Protocol server.The accuracy and reliability of ntpdate depends on the number of servers, the number of polls each time it is run and the interval between runs.The maintainers have...
  
  
• NTP pool
  NTP pool
  The NTP pool is a dynamic collection of networked computers that volunteer to provide highly accurate time via the Network Time Protocol to clients worldwide. The machines that are "in the pool" are part of the pool.ntp.org domain as well as of several subdomains divided by geographical zone and...
  
  , a collection of worldwide computers that provide a highly accurate time via the Network Time Protocol
• NTP server misuse and abuse
  NTP server misuse and abuse
  NTP server misuse and abuse covers a number of practices which cause damage or degradation to a Network Time Protocol server, ranging from flooding it with traffic or violating the server's access policy or the NTP . One incident was branded NTP vandalism in an open letter from Poul-Henning Kamp...
  
  
• Synchronization
  Synchronization
  Synchronization is timekeeping which requires the coordination of events to operate a system in unison. The familiar conductor of an orchestra serves to keep the orchestra in time....
  
  
• Time server

Other time synchronization protocols:

• Berkeley algorithm
  Berkeley algorithm
  The Berkeley algorithm is a method of clock synchronisation in distributed computing which assumes no machine has an accurate time source. It was developed by Gusella and Zatti at the University of California, Berkeley in 1989 and like Cristian's algorithm is intended for use within intranets.-...
  
  
• DAYTIME protocol
  DAYTIME
  The Daytime Protocol is a service in the Internet Protocol Suite, defined in 1983 in RFC 867. It is intended for testing and measurement purposes in computer networks....
  
  , older time synchronization protocol using TCP or UDP port 13
• ICMP Timestamp
  ICMP Timestamp
  The Timestamp is an ICMP message which is used for time synchronization. It consists of the originating timestamp.Message Format: * Type must be set to 13.* Code must be set to 0....
  
   and ICMP Timestamp Reply
  ICMP Timestamp Reply
  The Timestamp Reply is an ICMP message which replies to a Timestamp message. It consists of the originating timestamp sent by the sender of the Timestamp as well as a receive timestamp and a transmit timestamp.Message Format:...
  
  , older time synchronization protocol using ICMP
• Precision Time Protocol
  Precision Time Protocol
  The Precision Time Protocol is a protocol used to synchronize clocks throughout a computer network. On a local area network it achieves clock accuracy in the sub-microsecond range, making it suitable for measurement and control systems....
  
  
• TIME protocol
  TIME protocol
  The Time Protocol is a network protocol in the Internet Protocol Suite defined in 1983 in RFC 868. Its purpose is to provide a site-independent, machine readable date and time....
  
  , older time synchronization protocol using TCP or UDP port 37