In a distributed system, any clock synchronization algorithm has to synchronize the clocks periodically to maintain the accuracy of network time. The uncertainty of network delays and the unknown relative drift rate between computer's clocks are two major problems to synchronize clocks. Increasing the messages (clock readings) exchange rate can reduce the drift error, but it will increase the network load. If the network becomes congested, it will increase the delay uncertainty and the cell loss rate. This will decrease the synchronization accuracy. Therefore, it is a problem to predict as to how fast one needs to exchange the clock messages to achieve an expected accuracy of network time. We present a simple clock synchronization algorithm. Suppose the delay uncertainty and cell loss rate are given, we can clearly know how fast the message exchange rate can achieve and how accurate is the network time. Even though our measurement results show that the stability of our current computer clocks is worse than most assumptions in the literature on clock synchronization, our clock synchronization algorithm can still provide high synchronization accuracy by accurately estimating the relative drift rate between clocks. Here we also show how to monitor the quality of synchronization online. (C) 1999 Elsevier Science B.V. All rights reserved.
