Clock synchronization

Clock drift

Clock synchronization is a problem from computer science 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 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 Problems
2 Solutions
- 2.1 Cristian's Algorithm
- 2.2 Berkeley Algorithm
3 References

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 sytems 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 file server and the two machine have unsynchronized clocks, make might not make the correct decsions.

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 Internet Network Time Protocol (NTP) which is a layered client-server architecture based on UDP message passing.

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 propagation time.

Berkeley Algorithm

This algorithm is more suitable for systems where there 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 highlightes the fact that internal clocks may vary not only in the time they contain but also in the clock rate.

References

Martin Van Steen, Andrew S. Tanenbaum: Distributed Systems : Principles and Paradigms, Prentice Hall, ISBN 0–13–088893–1

Categories: Synchronization