Cristian's algorithm (introduced by
Flaviu Cristian in 1989)
is a method for
clock synchronization
Clock synchronization is a topic in computer science and engineering that aims to coordinate otherwise independent clocks. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift, caused by clocks ...
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
In telecommunications, round-trip delay (RTD) or round-trip time (RTT) is the amount of time it takes for a signal to be sent ''plus'' the amount of time it takes for acknowledgement of that signal having been received. This time delay includes pr ...
(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:
# ''P'' requests the time from ''S'' at time .
# After receiving the request from ''P'', ''S'' prepares a response and appends the time from its own clock.
# ''P'' receives the response at time then sets its time to be , where .
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
*
Allan variance
The Allan variance (AVAR), also known as two-sample variance, is a measure of frequency stability in clocks, oscillators and amplifiers. It is named after David W. Allan and expressed mathematically as \sigma_y^2(\tau).
The Allan deviation (ADE ...
*
Berkeley algorithm
*
Clock synchronization
Clock synchronization is a topic in computer science and engineering that aims to coordinate otherwise independent clocks. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift, caused by clocks ...
*
Daytime Protocol
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.
A host may connect to a server that supports the Daytime Protocol on either T ...
, older time synchronization protocol using TCP or UDP port 13
*
ICMP Timestamp and
ICMP Timestamp Reply, older time synchronization protocol using ICMP
*
International Atomic Time
International Atomic Time (abbreviated TAI, from its French name ) is a high-precision atomic coordinate time standard based on the notional passage of proper time on Earth's geoid. TAI is a weighted average of the time kept by over 450 ato ...
*
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 Name Syste ...
, 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 covers a number of practices which cause damage or degradation to a Network Time Protocol (NTP) server, ranging from flooding it with traffic (effectively a DDoS attack) or violating the server's access policy or the NT ...
*
ntpd
The Network Time Protocol daemon (ntpd) is an operating system program that maintains the system time in synchronization with time servers using the Network Time Protocol (NTP).
Description
The ntpd program is an operating-system daemon that s ...
,
OpenNTPD
OpenNTPD (also known as OpenBSD NTP Daemon) is a Unix 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
*
Precision Time Protocol
The Precision Time Protocol (PTP) 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. ...
*
Synchronization
*
Time Protocol
The Time Protocol is a network protocol in the Internet Protocol Suite defined in 1983 in RFC 868 by Jon Postel and K. Harrenstein. Its purpose is to provide a site-independent, machine readable date and time.
The Time Protocol may be implemented ...
, older time synchronization protocol using TCP or UDP port 37
*
Time server
Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, to ...
References
{{DEFAULTSORT:Cristian's Algorithm
Distributed algorithms
Synchronization