Cristian's algorithm

Cristian's algorithm (introduced by Flaviu Cristian in 1989)[1] is a method for clock synchronization 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 synchronization 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.

Description

Cristian's algorithm works between a process P, and a time server S connected to a time reference source. 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

This method assumes that the RTT is split equally between 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 by P is received, 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).

gollark: > Note The parameter reuse_address is no longer supported, as using SO_REUSEADDR poses a significant security concern for UDP. Explicitly passing reuse_address=True will raise an exception. Ah yes, thanks for arbitrarily removing things with no replacement, Python.
gollark: Excellent, via deployment of "bee memes" I have made it function somewhat.
gollark: I did not. The issue was resolved after I made it rethingy the file or something.
gollark: Well, not Python, but VSCode's python thing?
gollark: Why does Python keep saying that `self`, a highly extant variable, does not exist?

See also

References
  1. Cristian, F. (1989), "Probabilistic clock synchronization", Distributed Computing, Springer, 3 (3): 146–158, doi:10.1007/BF01784024
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.