An upper and a lower bound for tick synchronization

Abstract

The tick synchronization problem is defined and studied in the semi-synchronous complete network with n processes. An algorithm for the tick synchronization problem enables each process to make an estimate of real time close enough to those of other processes. It is assumed that the (real) time for message delivery is at most d and the time between any two consecutive steps of any process is in the interval [c, 1], where 0 < c ≤ 1. We define the precision of a tick synchronization algorithm to be the maximum difference between estimates of real time made by different processes, and propose it as a worst-case performance measure. We show that no such algorithm can guarantee precision less than [d-2/2c]. We also present an algorithm which achieves a precision of 2(n-1)/n([2d/e]+d/2)+1-e/c d+1. © 1992 IEEE.