HOME

TheInfoList



OR:

Clock synchronization is a topic in
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
and
engineering Engineering is the practice of using natural science, mathematics, and the engineering design process to Problem solving#Engineering, solve problems within technology, increase efficiency and productivity, and improve Systems engineering, s ...
that aims to coordinate otherwise independent
clock A clock or chronometer is a device that measures and displays time. The clock is one of the oldest Invention, human inventions, meeting the need to measure intervals of time shorter than the natural units such as the day, the lunar month, a ...
s. Even when initially set accurately, real clocks will differ after some amount of time due to
clock drift Clock drift refers to several related phenomena where a clock does not run at exactly the same rate as a reference clock. That is, after some time the clock "drifts apart" or gradually desynchronizes from the other clock. All clocks are subject to ...
, 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.


Terminology

In serial communication, clock synchronization can refer to clock recovery, which achieves frequency synchronization, as opposed to full phase synchronization. Such clock synchronization is used in synchronization in telecommunications and automatic baud rate detection. Plesiochronous or
isochronous A sequence of events is isochronous if the events occur regularly, or at equal time intervals. The term ''isochronous'' is used in several technical contexts, but usually refers to the primary subject maintaining a constant period or interval ( ...
operation refers to a system with frequency synchronization and loose constraints on phase synchronization. Synchronous operation implies a tighter synchronization based on time perhaps in addition to frequency.


Problems

As a result of the difficulties managing time at smaller scales, there are problems associated with
clock skew Clock skew (sometimes called timing skew) is a phenomenon in synchronous digital circuit systems (such as computer systems) in which the same sourced clock signal arrives at different components at different times due to gate or, in more advanc ...
that take on more complexity in
distributed computing Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers. The components of a distributed system commu ...
in which several computers will need to realize the same global time. For instance, in
Unix Unix (, ; trademarked as UNIX) is a family of multitasking, multi-user computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, a ...
systems, the '' make'' command is used to compile new or modified code and seeks to avoid recompiling 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 In computing, a file server (or fileserver) is a computer attached to a network that provides a location for shared disk access, i.e. storage of computer files (such as text, image, sound, video) that can be accessed by workstations within a co ...
and the two machines have unsynchronized clocks, the ''make'' program might not produce the correct results. Synchronization is required for accurate reproduction of
streaming media Streaming media refers to multimedia delivered through a Computer network, network for playback using a Media player (disambiguation), media player. Media is transferred in a ''stream'' of Network packet, packets from a Server (computing), ...
. Clock synchronization is a significant component of
audio over Ethernet In audio engineering, audio and broadcast engineering, broadcast engineering, Audio networking is the use of a Computer networking, network to distribute real-time digital audio. Audio Networking replaces bulky snake cables or audio-specific insta ...
systems.


Solutions

In a system with a central server, the synchronization solution is trivial; the server will dictate the system time. Cristian's algorithm and the Berkeley algorithm are potential solutions to the clock synchronization problem in this environment. In distributed computing, 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 The Network Time Protocol (NTP) is a networking protocol for clock synchronization between computer systems over packet-switched, variable-Network latency, latency data networks. In operation since before 1985, NTP is one of the oldest Intern ...
(NTP), which is a layered client-server architecture based on
User Datagram Protocol In computer networking, the User Datagram Protocol (UDP) is one of the core communication protocols of the Internet protocol suite used to send messages (transported as datagrams in Network packet, packets) to other hosts on an Internet Protoco ...
(UDP) message passing. Lamport timestamps and
vector clock A vector clock is a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, inter-process messages contain the state of the sending process's ...
s are concepts of the logical clock in distributed computing. In a
wireless network A wireless network is a computer network that uses wireless data connections between network nodes. Wireless networking allows homes, telecommunications networks, and business installations to avoid the costly process of introducing cables int ...
, the problem becomes even more challenging due to the possibility of collision of the synchronization packets on the wireless medium and the higher drift rate of clocks on low-cost wireless devices.


Berkeley algorithm

The Berkeley algorithm is suitable for systems where a
radio clock A radio clock or radio-controlled clock (RCC), and often colloquially (and incorrectly) referred to as an "atomic clock", is a type of Quartz clock, quartz clock or watch that is automatically Synchronization, synchronized to a time code transmi ...
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 Clock rate or clock speed in computing typically refers to the frequency at which the clock generator of a processor can generate pulses used to synchronize the operations of its components. It is used as an indicator of the processor's s ...
.


Clock-sampling mutual network synchronization

Clock-sampling mutual network synchronization (CS-MNS) is suitable for distributed and mobile applications. It has been shown to be scalable over mesh networks that include indirectly-linked non-adjacent nodes and is compatible with IEEE 802.11 and similar standards. It can be accurate to the order of a few microseconds but requires direct physical wireless connectivity with negligible link delay (less than 1 microsecond) on links between adjacent nodes, limiting the distance between neighboring nodes to a few hundred meters.


Cristian's algorithm

Cristian's algorithm relies on the existence of a time server. The time server maintains its clock by using a radio 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 is the behavior of radio waves as they travel, or are wave propagation, propagated, from one point to another in vacuum, or into various parts of the atmosphere. As a form of electromagnetic radiation, like light waves, radio w ...
time.


Satellite navigation systems

In addition to its use in navigation, the
Global Positioning System The Global Positioning System (GPS) is a satellite-based hyperbolic navigation system owned by the United States Space Force and operated by Mission Delta 31. It is one of the global navigation satellite systems (GNSS) that provide ge ...
(GPS) can also be used for clock synchronization. The accuracy of GPS time signals is ±10 nanoseconds. Using GPS (or other
satellite navigation A satellite navigation or satnav system is a system that uses satellites to provide autonomous geopositioning. A satellite navigation system with global coverage is termed global navigation satellite system (GNSS). , four global systems are ope ...
systems) for synchronization requires a receiver connected to an antenna with unobstructed view of the sky.


Inter-range Instrumentation Group time codes

IRIG timecodes are standard formats for transferring timing information. Atomic frequency standards and GPS receivers designed for precision timing are often equipped with an IRIG output. The standards were created by the Telecommunications Working Group of the United States military's Inter-Range Instrumentation Group (IRIG), the standards body of the Range Commanders Council. Work on these standards started in October 1956, and the original standards were accepted in 1960.


Network Time Protocol

Network Time Protocol The Network Time Protocol (NTP) is a networking protocol for clock synchronization between computer systems over packet-switched, variable-Network latency, latency data networks. In operation since before 1985, NTP is one of the oldest Intern ...
(NTP) is a highly robust protocol, widely deployed throughout the Internet. Well tested over the years, it is generally regarded as the state of the art in distributed time synchronization protocols for unreliable networks. It can reduce synchronization offsets to times of the order of a few milliseconds over the public Internet and to sub-millisecond levels over
local area network A local area network (LAN) is a computer network that interconnects computers within a limited area such as a residence, campus, or building, and has its network equipment and interconnects locally managed. LANs facilitate the distribution of da ...
s. A simplified version of the NTP protocol, Simple Network Time Protocol (SNTP), can also be used as a pure single-shot stateless primary/secondary synchronization protocol, but lacks the sophisticated features of NTP, and thus has much lower performance and reliability levels.


Precision Time Protocol

Precision Time Protocol The Precision Time Protocol (PTP) is a protocol for clock synchronization throughout a computer network with relatively high precision and therefore ''potentially'' high accuracy. In a local area network (LAN), accuracy can be sub-microsecon ...
(PTP) is a master/slave protocol for delivery of highly accurate time over local area networks.


Reference broadcast synchronization

The Reference Broadcast Time Synchronization (RBS) 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.


Reference Broadcast Infrastructure Synchronization

The Reference Broadcast Infrastructure Synchronization (RBIS) protocol is a master/slave synchronization protocol, like RBS, based on a receiver/receiver synchronization paradigm. It is specifically tailored to be used in IEEE 802.11 wireless networks configured in infrastructure mode (i.e., coordinated by an access point). The protocol does not require any modification to the access point.


Synchronous Ethernet

Synchronous Ethernet uses Ethernet in a synchronous manner such that when combined with synchronization protocols such as PTP in the case of the White Rabbit Project, sub-nanosecond synchronization accuracy is achieved.


Wireless ad hoc networks

Synchronization is achieved in
wireless ad hoc network A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, ...
s through sending synchronization messages in a multi-hop manner and each node progressively synchronizing with the node that is the immediate sender of a synchronization message. Examples include Flooding Time Synchronization Protocol (FTSP), and Harmonia, both able to achieve synchronization with accuracy on the order of microseconds.


Huygens

Researchers from Stanford and Google introduced Huygens, a probe-based, end-to-end clock synchronization algorithm. Huygens is implemented in software and thus can be deployed in
data center A data center is a building, a dedicated space within a building, or a group of buildings used to house computer systems and associated components, such as telecommunications and storage systems. Since IT operations are crucial for busines ...
s or in public cloud environments. By leveraging some key aspects of modern data centers and applying novel estimation algorithms and signal processing techniques, the Huygens algorithm achieved an accuracy of tens of nanoseconds even at high network load. The findings of this research are being tested in financial market applications.


See also

* Einstein synchronisation *
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 atomi ...
* Network Identity and Time Zone *
Synchronization (computer science) In computer science, synchronization is the task of coordinating multiple processes to join up or handshake at a certain point, in order to reach an agreement or commit to a certain sequence of action. Motivation The need for synchronization ...
* Time and frequency transfer *
Time signal A time signal is a visible, audible, mechanical, or electronic signal used as a reference to determine the time of day. Church bells or voices announcing hours of prayer gave way to automatically operated chimes on public clocks; however, au ...
*
Time standard A time standard is a specification for measuring time: either the rate at which time passes or points in time or both. In modern times, several time specifications have been officially recognized as standards, where formerly they were matters of cu ...
* Reference Broadcast Infrastructure Synchronization


References


Further reading

* * {{citation , title=Exploiting a Natural Network Effect for Scalable, Fine-grained Clock Synchronization , isbn=9781939133014 , url=https://www.usenix.org/conference/nsdi18/presentation/geng , access-date=2021-10-19 Synchronization Clocks Distributed computing problems