A Theory of Clock Synchronization (PhD thesis)

We consider the problem of clock synchronization in a system with uncertain message delays and clocks with bounded drift. To analyze this classical problem, we introduce the concept of synchronization graphs, and show that the tightest achievable synchronization at any given execution is characterized by the distances in the synchronization graph for that execution. Synchronization graphs are derived from information which is locally available for computation at the processors (local time of events and system specification), and can therefore be used by distributed algorithms. Using synchronization graphs, we obtain the first optimal on-line distributed algorithms for external clock synchronization, where the task of all processors is to estimate the reading of the local clock of a distinguished processor. The algorithms are optimal for all executions, rather than only for worst cases. The algorithm for systems with arbitrarily drifting clocks has high overhead; we prove that this phenomenon is unavoidable, namely any optimal general algorithm for external synchronization has unbounded space complexity. For systems with drift-free clocks (i.e., clocks that run at the rate of real time), we present a particularly simple and efficient algorithm. We also present results for internal synchronization, where the task of the processors in the system is to generate a synchronized ``tick.'' Our approach is robust in the sense it encompasses various system models, such as point-to-point or broadcast channels, communication links that may lose, duplicate and re-order messages, and crashing processors. In addition, synchronization graphs can be used to detect corrupted information.

Click here for proceedings version. Click here