Clock synchronization
Encyclopedia
Clock synchronization is a problem from computer science
and engineering
which deals with the idea that internal clock
s 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 clocks counting time at slightly different rates. There are several problems that occur as a repercussion of rate differences and several solutions, some being more appropriate than others in certain contexts.
In serial communication, some people use the term "clock synchronization" merely to discuss getting one metronome-like clock signal
to pulse at the same frequency as another one frequency synchronization and phase synchronization
. Such "clock synchronization" is used in synchronization in telecommunications
and automatic baud rate detection
.
in which several computers will need to realize the same global time.
For instance, in Unix
systems the make command is used to compile
new or modified code without the need to recompile unchanged code. The make command uses the clock of the machine it runs on to determine which source files need to be recompiled. If the sources reside on a separate file server
and the two machines have unsynchronized clocks, the make program might not produce the correct results.
the solution is trivial; the centralized server will dictate the system time. Cristian's algorithm
and the Berkeley Algorithm
are some solutions to the clock synchronization problem in a centralized server environment.
In a distributed system
the problem takes on more complexity because a global time is not easily known. The most used clock synchronization solution on the Internet is the Network Time Protocol (NTP)
which is a layered client-server architecture based on UDP message passing. Lamport timestamps
and Vector clocks
are concepts of the logical clocks in distributed systems.
or other accurate time source, then all other computers in the system stay synchronized with it. A time client will maintain its clock by making a procedure call to the time server. Variations of this algorithm make more precise time calculations by factoring in network radio propagation
time.
Often, any client whose clock differs by a value outside of a given tolerance is disregarded when averaging the results. This prevents the overall system time from being drastically skewed due to one erroneous clock.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and engineering
Engineering
Engineering is the discipline, art, skill and profession of acquiring and applying scientific, mathematical, economic, social, and practical knowledge, in order to design and build structures, machines, devices, systems, materials and processes that safely realize improvements to the lives of...
which deals with the idea that internal clock
Clock
A clock is an instrument used to indicate, keep, and co-ordinate time. The word clock is derived ultimately from the Celtic words clagan and clocca meaning "bell". A silent instrument missing such a mechanism has traditionally been known as a timepiece...
s of several computers may differ. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift
Clock drift
Clock drift refers to several related phenomena where a clock does not run at the exact right speed compared to another clock. That is, after some time the clock "drifts apart" from the other clock. This phenomenon is also used for instance in computers to build random number generators...
, caused by clocks counting time at slightly different rates. There are several problems that occur as a repercussion of rate differences and several solutions, some being more appropriate than others in certain contexts.
In serial communication, some people use the term "clock synchronization" merely to discuss getting one metronome-like clock signal
Clock signal
In electronics and especially synchronous digital circuits, a clock signal is a particular type of signal that oscillates between a high and a low state and is utilized like a metronome to coordinate actions of circuits...
to pulse at the same frequency as another one frequency synchronization and phase synchronization
Phase synchronization
Phase synchronization is the process by which two or more cyclic signals tend to oscillate with a repeating sequence of relative phase angles.Phase synchronisation is usually applied to two waveforms of the same frequency with identical phase angles with each cycle...
. Such "clock synchronization" is used in synchronization in telecommunications
Synchronization in telecommunications
Many services running on modern digital telecommunications networks require accurate synchronization for correct operation. For example, if switches do not operate with the same clock rates, then slips will occur and degrade performance...
and automatic baud rate detection
Automatic baud rate detection
Automatic baud rate detection refers to the process by which a receiving device determines the speed, code level, and stop bits of incoming data by examining the first character, usually a preselected sign-on character...
.
Problems
Besides the incorrectness of the time itself, there are problems associated with clock skew that take on more complexity in a distributed systemDistributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
in which several computers will need to realize the same global time.
For instance, in Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
systems the make command is used to compile
Compile
Compile may refer to:* Compile , a Japanese video game company founded in 1983 that specialized in shoot 'em up and computer puzzle game genres...
new or modified code without the need to recompile unchanged code. The make command uses the clock of the machine it runs on to determine which source files need to be recompiled. If the sources reside on a separate file server
File server
In computing, a file server is a computer attached to a network that has the primary purpose of providing a location for shared disk access, i.e. shared storage of computer files that can be accessed by the workstations that are attached to the computer network...
and the two machines have unsynchronized clocks, the make program might not produce the correct results.
Solutions
In a centralized systemCentralized system
In telecommunications, a centralized, or centralised system, is one in which most communications are routed through one or more major central hubs. Such a system allows certain functions to be concentrated in the system's hubs, freeing up resources in the peripheral units...
the solution is trivial; the centralized server will dictate the system time. Cristian's algorithm
Cristian's algorithm
Cristian's Algorithm 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...
and the Berkeley Algorithm
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 and like Cristian's algorithm is intended for use within intranets.-...
are some solutions to the clock synchronization problem in a centralized server environment.
In a distributed system
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
the problem takes on more complexity because a global time is not easily known. The most used clock synchronization solution on the Internet is the Network Time Protocol (NTP)
Network Time Protocol
The Network Time Protocol is a protocol and software implementation for synchronizing the clocks of computer systems over packet-switched, variable-latency data networks. Originally designed by David L...
which is a layered client-server architecture based on UDP message passing. Lamport timestamps
Lamport timestamps
The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and...
and Vector clocks
Vector clocks
Vector clocks are an algorithm for generating a partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, interprocess messages contain the state of the sending process's logical clock...
are concepts of the logical clocks in distributed systems.
Cristian's algorithm
Cristian's algorithm relies on the existence of a time server. The time server maintains its clock by using a radio clockRadio clock
A radio clock or radio-controlled clock is a clock that is synchronized by a time code bit stream transmitted by a radio transmitter connected to a time standard such as an atomic clock...
or other accurate time source, then all other computers in the system stay synchronized with it. A time client will maintain its clock by making a procedure call to the time server. Variations of this algorithm make more precise time calculations by factoring in network radio propagation
Radio propagation
Radio propagation is the behavior of radio waves when they are transmitted, or propagated from one point on the Earth to another, or into various parts of the atmosphere...
time.
Berkeley algorithm
This algorithm is more suitable for systems where a radio clock is not present, this system has no way of making sure of the actual time other than by maintaining a global average time as the global time. A time server will periodically fetch the time from all the time clients, average the results, and then report back to the clients the adjustment that needs be made to their local clocks to achieve the average. This algorithm highlights the fact that internal clocks may vary not only in the time they contain but also in the clock rate.Often, any client whose clock differs by a value outside of a given tolerance is disregarded when averaging the results. This prevents the overall system time from being drastically skewed due to one erroneous clock.
Network Time Protocol
This algorithm is a class of mutual network synchronization algorithm in which no master or reference clocks are needed. All clocks equally participate in the synchronization of the network by exchanging their timestamps using regular beacon packets.Clock Sampling Mutual Network Synchronization
CS-MNS is suitable for distributed and mobile applications. It has been shown to be scalable, accurate in the order of few microseconds, and compatible to IEEE 802.11 and similar standards.Precision Time Protocol
PTP is used in measurement and control systems in local area networks and can achieve sub-microsecond accuracy.Reference broadcast synchronization
This algorithm is often used in wireless networks and sensor networks. In this scheme, an initiator broadcasts a reference message to urge the receivers to adjust their clocks.See also
- International Atomic TimeInternational Atomic TimeInternational Atomic Time is a high-precision atomic coordinate time standard based on the notional passage of proper time on Earth's geoid...
- Network Identity and Time ZoneNITZNITZ, or Network Identity and Time Zone, is a mechanism for provisioning local time and date, as well as network provider identity information to mobile devices via a wireless network. NITZ has been part of the official GSM standard since phase 2+ release 96...
- Network Time ProtocolNetwork Time ProtocolThe Network Time Protocol is a protocol and software implementation for synchronizing the clocks of computer systems over packet-switched, variable-latency data networks. Originally designed by David L...
- Precision Time ProtocolPrecision Time ProtocolThe Precision Time Protocol 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....
- Vector clocksVector clocksVector clocks are an algorithm for generating a partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, interprocess messages contain the state of the sending process's logical clock...
- Einstein synchronisationEinstein synchronisationEinstein synchronisation is a convention for synchronising clocks at different places by means of signal exchanges. This synchronisation method was used already by telegraphers in the middle 19th century, but was popularized by H. Poincaré and A...