Cristian's algorithm

Cristian's algorithm

Cristian's Algorithm (introduced by Flaviu Cristian in 1989)[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.

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).

References

  1. ^ Cristian, F. (1989), "Probabilistic clock synchronization", Distributed Computing (Springer) 3 (3): 146–158, doi:10.1007/BF01784024, http://www.springerlink.com/content/j5250h34013874jv/ 

See also

Other time synchronization protocols:


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • 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 [Citation… …   Wikipedia

  • 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 …   Wikipedia

  • Chaitin's constant — In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that informally represents the probability that a randomly constructed program will halt. These numbers are formed from …   Wikipedia

  • Deadlock — This article is about the computer science concept. For other uses, see Deadlock (disambiguation). A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often… …   Wikipedia

  • Concolic testing — (a portmanteau of concrete and symbolic) is a hybrid software verification technique that interleaves concrete execution (testing on particular inputs) with symbolic execution, a classical technique that treats program variables as symbolic… …   Wikipedia

  • Bead sort — is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002, and published in The Bulletin of the European Association for Theoretical Computer Science. Both digital and analog hardware… …   Wikipedia

  • Michael Dinneen — Michael J. Dinneen is an American New Zealand mathematician and computer scientist working as a senior lecturer at the University of Auckland, New Zealand. Co director of the Centre for Discrete Mathematics and Theoretical Computer Science.… …   Wikipedia

  • Ackermann function — In recursion theory, the Ackermann function or Ackermann Péter function is a simple example of a general recursive function that is not primitive recursive. General recursive functions are also known as computable functions. The set of primitive… …   Wikipedia

  • Collatz conjecture — Directed graph showing the orbits of small numbers under the Collatz map. The Collatz conjecture is equivalent to the statement that all paths eventually lead to 1 …   Wikipedia

  • Gregory Chaitin — Born 1947 (1947) Chicago[1] Residence …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”