Cristian's algorithm

Last updated

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.

Contents

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

Related Research Articles

The Internet Control Message Protocol (ICMP) is a supporting protocol in the Internet protocol suite. It is used by network devices, including routers, to send error messages and operational information indicating success or failure when communicating with another IP address, for example, an error is indicated when a requested service is not available or that a host or router could not be reached. ICMP differs from transport protocols such as TCP and UDP in that it is not typically used to exchange data between systems, nor is it regularly employed by end-user network applications.

The Real-time Transport Protocol (RTP) is a network protocol for delivering audio and video over IP networks. RTP is used in communication and entertainment systems that involve streaming media, such as telephony, video teleconference applications including WebRTC, television services and web-based push-to-talk features.

The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite. It originated in the initial network implementation in which it complemented the Internet Protocol (IP). Therefore, the entire suite is commonly referred to as TCP/IP. TCP provides reliable, ordered, and error-checked delivery of a stream of octets (bytes) between applications running on hosts communicating via an IP network. Major internet applications such as the World Wide Web, email, remote administration, and file transfer rely on TCP, which is part of the Transport Layer of the TCP/IP suite. SSL/TLS often runs on top of TCP.

In computing, traceroute and tracert are computer network diagnostic commands for displaying possible routes (paths) and measuring transit delays of packets across an Internet Protocol (IP) network. The history of the route is recorded as the round-trip times of the packets received from each successive host in the route (path); the sum of the mean times in each hop is a measure of the total time spent to establish the connection. Traceroute proceeds unless all sent packets are lost more than twice; then the connection is lost and the route cannot be evaluated. Ping, on the other hand, only computes the final round-trip times from the destination point.

<span class="mw-page-title-main">Network Time Protocol</span> Standard protocol for synchronizing time across devices

The Network Time Protocol (NTP) is a networking protocol for clock synchronization between computer systems over packet-switched, variable-latency data networks. In operation since before 1985, NTP is one of the oldest Internet protocols in current use. NTP was designed by David L. Mills of the University of Delaware.

STUN is a standardized set of methods, including a network protocol, for traversal of network address translator (NAT) gateways in applications of real-time voice, video, messaging, and other interactive communications.

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 counting time at slightly different rates. There are several problems that occur as a result of clock rate differences and several solutions, some being more acceptable than others in certain contexts.

The Discard Protocol is a service in the Internet Protocol Suite defined in RFC 863. It was designed for testing, debugging, measurement, and host-management purposes.

The Echo Protocol is a service in the Internet Protocol Suite defined in RFC 862. It was originally proposed for testing and measurement of round-trip times in IP networks.

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 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. PTP is employed to synchronize financial transactions, mobile phone tower transmissions, sub-sea acoustic arrays, and networks that require precise timing but lack access to satellite navigation signals.

Network address translation traversal is a computer networking technique of establishing and maintaining Internet protocol connections across gateways that implement network address translation (NAT).

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

A UDP flood attack is a volumetric denial-of-service (DoS) attack using the User Datagram Protocol (UDP), a sessionless/connectionless computer networking protocol.

TSIG is a computer-networking protocol defined in RFC 2845. Primarily it enables the Domain Name System (DNS) to authenticate updates to a DNS database. It is most commonly used to update Dynamic DNS or a secondary/slave DNS server. TSIG uses shared secret keys and one-way hashing to provide a cryptographically secure means of authenticating each endpoint of a connection as being allowed to make or respond to a DNS update.

ntpdate is a computer program used to quickly synchronize and set computers' date and time by querying a Network Time Protocol (NTP) server. It is available for a wide variety of unix-like operating systems.

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. Like Cristian's algorithm, it is intended for use within intranets.

Flaviu Cristian was a Romanian-American computer scientist noted for his work in distributed systems and, in particular, the development of a method for clock synchronisation which bears his name, Cristian's algorithm.

timed is an operating system program that maintains the system time in synchronization with time servers using the Time Synchronization Protocol (TSP) developed by Riccardo Gusella and Stefano Zatti. Gusella and Zatti had done earlier related work on their TEMPO algorithm. The Time Synchronization Protocol specification refers an election algorithm and a synchronization mechanism specified in other technical reports listed as "to appear".

chrony An implementation of the Network Time Protocol

chrony is an implementation of the Network Time Protocol (NTP). It's an alternative to ntpd, which is a reference implementation of NTP. It runs on Unix-like operating systems and is released under the GNU GPL v2. It's the default NTP client and server in Red Hat Enterprise Linux 8 and SUSE Linux Enterprise Server 15, and available in many Linux distributions.

References

  1. ↑ Cristian, Flaviu (1989), "Probabilistic clock synchronization" (PDF), Distributed Computing , Springer, 3 (3): 146–158, doi:10.1007/BF01784024, S2CID   3170166
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.