Cristian's algorithm

From Wikipedia, the free encyclopedia

Cristian's Algorithm^[1] 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.

[edit] 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 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).

[edit] References

v • d • e Major fields of Computer Science Mathematical foundations Mathematical logic · Set theory · Number theory · Graph theory · Type theory · Category theory · Numerical analysis Theory of computation Automata theory · Computability theory · Computational complexity theory · Quantum computing theory Algorithms and data structures Analysis of algorithms · Algorithms · Algorithm design · Data Structures · Computational geometry Programming languages and compilers Parsers · Compilers · Interpreters · Programming languages · Procedural programming · Object-oriented programming Concurrent, parallel, and distributed systems Concurrency · Distributed computing · Parallel computing · Grid computing Software engineering Requirements analysis · Software design · Computer programming · Formal methods · Software testing · Software development System architecture Computer architecture · Computer organization · Operating systems Telecommunication & Networking Computer audio · Routing · Network topology · Cryptography Databases Data mining · Relational databases · SQL Artificial intelligence Automated reasoning · Computational linguistics · Computer vision · Evolutionary computation · Machine learning · Natural language processing · Robotics Computer graphics Visualization · Image processing Human computer interaction Computer accessibility · User interfaces · Wearable computing · Ubiquitous computing · Virtual reality Scientific computing Artificial life · Bioinformatics · Cognitive Science · Computational chemistry · Computational neuroscience · Computational physics · Numerical algorithms · Symbolic mathematics