A precise clock synchronization protocol

A distributed clock synchronization protocol is presented which achieves a very high precision without the need for very frequent resynchronizations. The protocol tolerates failures of the clocks: clocks may be too slow or too fast, exhibit omission failures and report inconsistent values. Synchronization takes place in synchronization rounds as in many other synchronization protocols. At the end of each round, clock times are exchanged between the clocks. Each clock applies a convergence function (CF) to the values obtained. This function estimates the difference between its clock and an average clock and corrects its clock accordingly. Clocks are corrected for drift relative to this average clock during the next synchronization round. The protocol is based on the assumption that clock reading errors are small with respect to the required precision of synchronization. It is shown that the CF resynchronizes the clocks with high precision even when relatively large clock drifts are possible. The CF of the algorithm exploits the properties of a matrix that contains the differences between all clocks in the system. All correct processors have access to identical copies of this matrix which is disseminated by an underlying reliable message protocol. It is shown that the drift-corrected clocks remain synchronized until the end of the next synchronization round. The maximum length of a synchronization round mainly depends on the precision with which the clocks are resynchronized and on the maximum magnitude of the second time derivative of the function that describes a clock. The stability of the protocol is proven, i.e., it is shown that drift of the clocks with respect to physical time is bounded.