Rafail Ostrovsky - Publications

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