LOW-COST CLOCK SYNCHRONIZATION

We show how synchronized clocks can be realized in a distributed syste m as a byproduct of a common communication paradigm where processors p eriodically perform broadcasts. Our approach decouples the precision c oncern of clock synchronization - limiting how much correct clocks can differ from each other - from the accuracy concern - limiting the rat e at which any correct clock may drift from real time. Given a system that guarantees only precision, we develop a protocol whereby high acc uracy can be achieved on demand. In this manner, the ''lazy'' protocol we obtain incurs the cost of high accuracy only when needed while kee ping the basic synchronization procedure extremely simple and cheap.