Low-cost clock synchronization

Summary We show how synchronized clocks can be realized in a distributed system as a byproduct of a common communication paradigm where processors periodically perform broadcasts. Our approach decouples theprecision concern of clock synchronization—limiting how much correct clocks can differ from each other—from theaccuracy concern—limiting the rate at which any correct clock may drift from real time. Given a system that guarantees only precision, we develop a protocol whereby high accuracy can be achieved on demand. In this manner, the lazy protocol we obtain incurs the cost of high accuracy only when needed while keeping the basic synchronization procedure extremely simple and cheap.Rogério Drummond is Associate Professor of Computer Science at the Universidade de Campinas (Unicamp), Brazil. He received his Ph.D. in computer science from Cornell University in 1986. He has previously worked on distributed fault-tolerant computing, such as the present paper. Currently, he heads the A_HAND project which aims to provide an object-oriented distributed programming environment for the development of very large software systems.Özalp Babaolu is Professor of Computer Science at the University of Bologna, Italy. His research interests include distributed algorithms, fault tolerance and parallel computing. He received a BS in electrical engineering from George Washington University, Washington, D.C. in 1976. From the University of California, Berkeley, he received a MS in 1977 and a Ph.D. in 1981, both in computer science. While at Berkeley, he designed and implemented the virtual memory extensions to BSD Unix. From 1981 to 1987 he was on the faculty at the Department of Computer Science, Cornell University.Partial support for this work was provided by the National Science Foundation under Grant DCR-86-01864, AT&T under a Foundation Grant, the Commission of the European Communities under the ESPRIT Programme Basic Research Action Number 3092 (Predictably Dependable Computing Systems) and the Italian Ministry of University and Research. Drummond was partially supported through a Fellowship from the CAPES Agency of the Government of Brazil