A new probabilistic algorithm for clock synchronization
- 7 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
WE PRESENT A NEW AVERAGING PROBABLISTIC CLOCK SYNCHRONIZATION ALGORITHM, BASED ON THE REDUNDANT TRANSMISSION OF MULTIPLE SYNCHRONIZATION MESSAGES, THAT CAN GUARANTEE A MUCH LOWER UPPER BOUND ON THE DEVIATION BETWEEN CLOCKS THAN MOST EXISTING ALGORITHMS. OUR ALGORITHM IS PROBABLISTIC IN THE SENSE THAT THE UPPER BOUND ON THE DEVIATION THAT IT GUARANTEES HAS A PROBABILITY OF INVALIDITY ASSOCIATED WITH IT. THE PROBABILITY OF INVALIDITY, I.E., THE PROBABILITY THAT THE DEVIATION EXCEEDS THE GUARANTEED MAXIMUM DEVIATION, MAY HOWEVER BE MADE EXTREMELY SMALL BY SUFFICIENTLY INCREASING THE NUMBER OF MESSAGES TRANSMITTED. WE PROVE THAT AN UPPER BOUND ON THE PROBABILITY OF INVALIDITY DECREASES EXPONENTIALLY WITH THE NUMBER OF MESSAGES, I.E., THE PROBABILITY OF INVALIDITY ITSELF DECREASES EXPONENTIALLY OR BETTER.Keywords
This publication has 11 references indexed in Scilit:
- A new probabilistic algorithm for clock synchronizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A probabilistic approach to distributed clock synchronizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Clock Synchronization in Distributed Real-Time SystemsIEEE Transactions on Computers, 1987
- On the possibility and impossibility of achieving clock synchronizationJournal of Computer and System Sciences, 1986
- Synchronizing clocks in the presence of faultsJournal of the ACM, 1985
- An upper and lower bound for clock synchronizationInformation and Control, 1984
- A new fault-tolerant algorithm for clock synchronizationPublished by Association for Computing Machinery (ACM) ,1984
- Fault-tolerant clock synchronizationPublished by Association for Computing Machinery (ACM) ,1984
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978
- SIFT: Design and analysis of a fault-tolerant computer for aircraft controlProceedings of the IEEE, 1978