**
Optimal and Efficient Clock Synchronization Under Drifting Clocks
**

*
Rafail Ostrovsky, Boaz Patt-Shamir
*

**
Abstract:
**
We consider the classical problem of clock synchronization in
distributed systems. Previously, this problem was solved optimally
and efficiently only in the case when all individual clocks are
non-drifting, i.e., only for systems where all clocks advance at the
rate of real time. In this paper, we present a new optimal algorithm
for drifting clocks, which is the first optimal algorithm to solve the
problem efficiently: clock drift bounds and message latency bounds may
be arbitrary; the computational complexity depends on the
communication pattern of the system, which is bounded by a polynomial
in the network size for most systems. More specifically, we show new
optimal synchronization algorithm with computational complexity
polynomial in the maximal number of * live messages*, namely the
number of messages known to be sent but not received, and the relative
speed of processors.
Our result has two consequences. From the theoretical standpoint, it
refines the known bounds for optimal synchronization. But even more
importantly, it enables us to derive new optimal algorithms that are
reasonably efficient for most practical systems.

**comment:**
Appeared
in Proceedings of Eeighteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-99)

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |