Optimal clock synchronization under different delay assumptions

Abstract

The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and consist 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 tailored for each specific delay assumption. Optimal clock synchronization algorithms are derived for several types of delay assumptions by appropriately tuning the third component. The delay assumptions include lower and upper delay bounds, no bounds at all, and bounds on the difference of the delay in opposite directions. In addition, our model handles systems where some processors are connected by broadcast networks in which every message arrives at all the processors at approximately the same time. A composition theorem allows combinations of different assumptions for different links or even for the same link; such mixtures are common in practice. Our results achieve the best possible precision in each execution. This notion of optimality is stronger than the more common notion of worst-case optimality. The new notion of optimality applies to systems where the worst-case behavior of any clock synchronization algorithm is inherently unbounded.