Probabilistic Internal Clock Synchronization

We propose an improved probabilistic method for reading remote clocks in systems subject to unbounded communication delays and use this method to design a family of fault-tolerant probabilistic internal clock synchronization protocols. The members of this family differ in the failure classes they tolerate, from crash to arbitrary. Because of probabilistic reading, our protocols achieve better synchronization precisions than those achievable by previously known deterministic algorithms. Another advantage of the proposed protocols is that they use a linear, instead of quadratic, number of messages, and that message exchanges are staggered in time instead of all happening in narrow synchronization intervals. The envelope and drift rates of the synchronized clocks are proven to be optimal. 1 Introduction Most distributed systems encountered in practice are asynchronous, in that they do not guarantee a bound on message communication delays. Traditional deterministic, fault-tolerant clock s..