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