OPTIMAL CLOCK SYNCHRONIZATION UNDER DIFFERENT DELAY ASSUMPTIONS

The problem of achieving optimal clock synchronization in a communicat ion network with arbitrary topology and perfect clocks (that do not dr ift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and cons ist of three major components. The first component holds for any type of delay assumptions; the second component holds for a large, natural family of local delay assumptions; the third component must be tailore d for each specific delay assumption. Optimal clock synchronization al gorithms are derived for several types of delay assumptions by appropr iately tuning the third component. The delay assumptions include lower and upper delay bounds, no bounds at all, and bounds on the differenc e of the delay in opposite directions. In addition, our model handles systems where some processors are connected by broadcast networks in w hich every message arrives at all the processors at approximately the same time. A composition theorem allows combinations of different assu mptions for different links or even for the same link; such mixtures a re common in practice. Our results achieve the best possible precision in each execution. This notion of optimality is stronger than the mor e common notion of worst-case optimality. The new notion, of optimalit y applies to systems where the worst-case behavior of any clock synchr onization algorithm is inherently unbounded.