Saad Biaz and Jennifer L. Welch

We consider the problem of synchronizing the clocks of processors in a failure-free distributed system when the hardware clocks do not drift but there is uncertainty in the message delays. Our goal is to develop closed form expressions for how closely the clocks can be synchronized. For an arbitrary undirected topology with arbitrary (symmetric) uncertainties, we prove a lower bound of diam/2 on the closeness of synchronization achievable, where diam is the diameter of the graph when the edges are weighted with the uncertainties. We then consider the class of topologies described as k-ary m-cubes, both with and without wrap-around. We assume that every edge has the same uncertainty, u. For the k-ary m-cube without wrap-around, we show that our lower bound diam/2 = um(k-1)/2 is tight, by analyzing the synchronization achieved by a simple algorithm. Since chains, meshes, and hypercubes are special cases of this topology, we have tight bounds for them. For the k-ary m-cube with wrap-around, we show using the same algorithm that our lower bound diam/2 = u*m*floor(k/2)/2 is tight when k is even and is almost tight when k is odd. This result implies tight or almost tight bounds for rings and tori.