Convergence function for drift-corrected clock synchronization protocols

A distributed fault-tolerant convergence function is proposed to resynchronize clocks with high precision. The convergence function can be used in conjunction with drift corrections, which significantly increases the period between resynchronizations. This is important when clock drifts are large, because clock synchronization overhead then becomes intolerable. Clock differences are disseminated by a reliable message protocol after the clock values are exchanged. All correct clocks then have identical copies of a matrix of clock differences. Matrix elements of correct clocks satisfy several relations. A subset of clocks that satisfy these relations defines an average clock. The adjustment for each clock is calculated for protocols with and without drift corrections. The influence of incorrect clocks on the average clock is shown to be bounded. The resynchronization is precise if clock reading errors are small, including uncertainties in transmission delays. Incorrect clocks may run too slow or too fast, exhibit omission failures, or report inconsistent values.