Clock synchronization

Clock synchronization

Clock synchronization is a problem from computer science and engineering which deals with the idea that internal clocks 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.[1]

In serial communication, some people[2] 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.

Contents

Problems

Besides the incorrectness of the time itself, there are problems associated with clock skew that take on more complexity in a distributed system 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.

Solutions

In a centralized system 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.

Cristian's algorithm

Cristian's algorithm relies on the existence of a time server.[3] 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 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.[4]

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

References

  1. ^ Tanenbaum, Andrew S.; Maarten van Steen (2002), Distributed Systems : Principles and Paradigms, Prentice Hall, ISBN 0-13-088893-1 
  2. ^ "Transmission on a Serial Line"
  3. ^ Cristian, F. (1989), "Probabilistic clock synchronization", Distributed Computing (Springer) 3 (3): 146–158, doi:10.1007/BF01784024, http://www.springerlink.com/content/j5250h34013874jv/ 
  4. ^ Rentel, C.; Kunz, T. (March 2005), A clock-sampling mutual network time-synchronization algorithm for wireless ad hoc networks, "A clock-sampling mutual network synchronization algorithm for wireless ad hoc networks", IEEE Wireless Communications and Networking Conference (IEEE Press) 1: 638–644, doi:10.1109/WCNC.2005.1424575, ISBN 0-7803-8966-2, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1424575 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Synchronization — Synchrony redirects here. For linguistic synchrony, see Synchronic analysis. For the X Files episode, see Synchrony (The X Files). For similarly named concepts, see Synchronicity (disambiguation). Not to be confused with data… …   Wikipedia

  • Clock network — A clock network or clock system is a set of clocks designed to always show exactly the same time by communicating with each other. Clock networks usually include a central master clock kept in sync with an official time source, and one or more… …   Wikipedia

  • Clock generator — A desktop PC clock generator, based on the chip ICS 952018AF and 14.3 MHz resonator (on the left) …   Wikipedia

  • 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 rate clocks then slips will occur degrading performance.… …   Wikipedia

  • Clock — For other uses, see Clock (disambiguation). Timepiece redirects here. For the Kenny Rogers album, see Timepiece (album). Platform clock at King s Cross railway station, London …   Wikipedia

  • 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. Although the word signal… …   Wikipedia

  • Clock skew — Contents 1 In circuit design 1.1 Harmful skew 1.2 Beneficial skew 2 On a network 3 Interfaces …   Wikipedia

  • Clock distribution network — In a synchronous digital system, the clock signal is used to define a time reference for the movement of data within that system. The clock distribution network (or clock tree, when this network forms a tree) distributes the clock signal(s) from… …   Wikipedia

  • Clock hypothesis — The clock hypothesis is an assumption in special relativity. It states that the rate of a clock doesn t depend on its acceleration but only on its instantaneous velocity. This is equivalent to stating, that a clock moving along a path P measures… …   Wikipedia

  • synchronization — A technique of timing the delivery of fires by placing all units on a common time. The synchronized clock uses a specific hour and minute based on either local or universal time. Local time is established using the local time zone …   Military dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”