📑 Table of Contents▼

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

edit

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 at time t0.
  2. After receiving the request from P, S prepares a response and appends the time T from its own clock.
  3. P receives the response at time t1 then sets its time to be T + RTT/2, where RTT=t1-t0.

If the RTT is actually split equally between request and response, the synchronisation is error-free. But due to unpredictable influences, this assumption is regularly not true. Longer RTTs indicate interference that is generally asymmetrical. Offset and jitter of the synchronisation are thus minimised by selecting suitable RTT from a set of many request/response pairs. Whether an RTT can be accepted at a given time depends on the drift of the clock and on the statistics of the RTT. These quantities can be measured in the course of synchronisation, which optimises the method by itself.

See also

edit

References

edit
  1. ^ Cristian, Flaviu (1989), "Probabilistic clock synchronization" (PDF), Distributed Computing, 3 (3), Springer: 146–158, doi:10.1007/BF01784024, S2CID 3170166

📚 Artikel Terkait di Wikipedia

Clock synchronization

trivial; the server will dictate the system time. Cristian's algorithm and the Berkeley algorithm are potential solutions to the clock synchronization

Berkeley algorithm

Like Cristian's algorithm, it is intended for use within intranets. Unlike Cristian's algorithm, the server process in the Berkeley algorithm, called

Cristian (disambiguation)

Cristian is a given name. Cristian may also refer to: Cristian, Brașov Cristian, Sibiu Cristian's algorithm This disambiguation page lists articles associated

List of algorithms

An algorithm is a fundamental set of rules or defined procedures that are typically designed and used to be a simpler way to solve a specific problem

Flaviu Cristian

bears his name, Cristian's algorithm. He was born in 1951 in Cluj, in the Transylvania region of Romania, the son of Ilie and Rafila Cristian. After graduating

Time complexity

takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that

Cristian Calude

1088/1402-4896/aaf36a. ISSN 0031-8949. Calude, Cristian S.; Dumitrescu, Monica (7 June 2018). "A probabilistic anytime algorithm for the halting problem". Computability

List of metaphor-based metaheuristics

metaheuristics and swarm intelligence algorithms, sorted by decade of proposal. Simulated annealing is a probabilistic algorithm inspired by annealing, a heat