AbstractThis paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. Assuming a fault-tolerant authentication protocol, the algorithms tolerate both link and processor failures of any type. The algorithm for maintaining synchronization works for arbitrary networks (rather than just completely connected networks) and tolerates any number of processor or communication link faults as long as the correct processors remain connected by fault-free paths. It thus represents an improvement over other clock synchronization algorithms such as those of Lamport and Melliar-Smith [1985] and Welch and Lynch [1988], although, unlike them, it does require an authentication protocol to handle Byzantine faults. Our algorithm for allowing new processors to join requires that more than half the processors be correct, a requirement that is provably necessary. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distributed Systems; C.4 [Performance of Systems]; D.4.1 [Operating Systems]: Process Management -- synchronization; D.4.5 [Operating Systems]: Reliability -- fault-tolerance
General Terms: General Terms: Algorithms, performance, reliability, theory
Additional Key Words and Phrases: Byzantine failures, clock synchronization, fault-tolerance, time-of-day clock
Selected references
- Danny Dolev, Joseph Y. Halpern, Barbara Simons, and H. Raymond Strong. A new look at fault-tolerant network routing. Information and Computation, 72(3):180-196, March 1987.
- Leslie Lamport and P. M. Melliar-Smith. Synchronizing clocks in the presence of faults. Journal of the ACM, 32(1):52-78, January 1985.
- Jennifer Lundelius and Nancy Lynch. An upper and lower bound for clock synchronization. Information and Control, 62(2/3):190-204, August/September 1984.
- M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, April 1980.
- T. K. Srikanth and Sam Toueg. Optimal clock synchronization. Journal of the ACM, 34(3):626-645, July 1987.
- Jennifer Lundelius Welch and Nancy A. Lynch. A new fault-tolerance algorithm for clock synchronization. Information and Computation, 77(1):1-36, April 1988.