Fault-tolerant clock synchronization

ABSTRACT

This 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. The algorithms tolerate both link and node failures of any type. The algorithm for maintaining synchronization will work 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 [LM1,LM2,LL1]. Our algorithm for allowing new processors to join requires that more than half the processors be correct, a requirement which is provably necessary.

REFERENCES

• 1: Danny Dolev , Joe Halpern , Barbara Simons , Ray Strong, A new look at fault tolerant network routing, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.526-535, December 1984 [doi>10.1145/800057.808723]
• 2: Danny Dolev , Joe Halpern , H. Raymond Strong, On the possibility and impossibility of achieving clock synchronization, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.504-511, December 1984 [doi>10.1145/800057.808720]
• 3: D.Dolev and H. R. Strong, Authenticated algorithms for Byzantine agreement, SIAM J. of Computing, 12:4, 1983, pp. 656-666.
• 4: J.Y. Halpern, B. B. Simons, and H. R. Strong, An efficient fault-tolerant algorithm for clock synchronization, IBM RJ4094, 1983.
• 5: L. Lamport and P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, SRI International Report, 1982.
• 6: Leslie Lamport , P. M. Melliar-Smith, Byzantine clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.68-74, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806737]
• 7: Jennifer Lundelius , Nancy Lynch, A new fault-tolerant algorithm for clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.75-88, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806738]
• 8: J. Lundelius and N. Lynch, An upper lower bound for clock synchronization, unpublished manuscript, 1984.
• 9: K. Marzullo, Loosely-coupled distributed services: a distributed time system, Ph.D. dissertation, Stanford University, 1983.
• 10: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Management, Performance, Reliability