Probabilistic approach to distributed clock synchronization

Abstract

A probabilistic method is proposed for reading remote clocks in distributed systems subject to unbounded random communication delays. The method can achieve clock synchronization precisions superior to those attainable by previously published clock synchronization algorithms. The method can be used to improve the precision of both internal and external synchronization algorithms. The approach is probabilistic because it does not guarantee that a processor can always read a remote clock with an a priori specified precision; however, by retrying a sufficient number of times, a process can read the clock of another process with a given precision with a probability as close to one as desired. An important characteristic of the method is that, when a process succeeds in reading a remote clock, it knows the actual reading precision achieved. The use of the remote clock reading methods is illustrated by presenting a time service which maintains externally (and, hence, internally) synchronized clocks in the presence of process, communication, and clock failures.