A theory of clock synchronization (extended abstract)
Boaz Patt-Shamir, Sergio Rajsbaum · 1994
We consider the problem of clock synchronization with uncertain message delays and bounded clock drifts. To analyze this classical problem we introduce a characterization theorem for the tightest achievable estimate of the readings of a remote clock in any given execution of the system. Using this theorem, we obtain the first optimal on-line distributed algorithms for clock synchronization. The algorithms are optimal for all executions, rather than only worst cases. The general algorithm for systems with drifting clocks has high space overhead, which is unavoidable, as we show. For systems with drift-free clocks (i.e., clocks that run at the rate of real time), we present a remarkably simple and efficient algorithm. The discussion focuses on the variant where one of the clocks shows real time, but we present results also for the case where real time...