Probabilistic internal clock synchronization
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.Keywords
This publication has 5 references indexed in Scilit:
- Continuous clock amortization need not affect the precision of a clock synchronization algorithmPublished by Association for Computing Machinery (ACM) ,1990
- Probabilistic clock synchronizationDistributed Computing, 1989
- A new fault-tolerant algorithm for clock synchronizationInformation and Computation, 1988
- Optimal clock synchronizationJournal of the ACM, 1987
- Synchronizing clocks in the presence of faultsJournal of the ACM, 1985