A new fault-tolerant algorithm for clock synchronization

ABSTRACT

We describe a new fault-tolerant algorithm for solving a variant of Lamport's clock synchronization problem. The algorithm is designed for a system of distributed processes that communicate by sending messages. Each process has its own read-only physical clock whose drift rate from real time is very small. By adding a value to its physical clock time, the process obtains its local time. The algorithm solves the problem of maintaining closely synchronized local times, assuming that processes' local times are closely synchronized initially. The algorithm is able to tolerate the failure of just under a third of the participating processes. It maintains synchronization to within a small constant, whose magnitude depends upon the rate of clock drift, the message delivery time, and the inital closeness of synchronization. We also give a characterization of how far the clocks drift from real time. Reintegration of a repaired process can be accomplished using a slight modification of the basic algorithm. A similar style algorithm can also be used to achieve synchronization initially.

REFERENCES

• 1: 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]
• 2: D. Dolev, N. Lynch, S. Pinter, E. Stark and W. Weihl, Reaching approximate agreement in the presence of faults, Proceedings of the Third Annual IEEE Symposium on Distributed Software and Database Systems (1983).
• 3: C. Dwork, N. Lynch and L. Stockmeyer. Consensus in the presence of partial synchrony, to appear in Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (1984).
• 4: Joseph Y. Halpern , Barbara Simons , Ray Strong , Danny Dolev, Fault-tolerant clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.89-102, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806739]
• 5: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 6: L. Lamport and P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, SRI International Report (March 1982).
• 7: J. Lundelius, Synchronizing clocks in a distributed system, S.M. thesis, MIT (in progress).
• 8: K. Marzullo, Loosely-coupled distributed services: a distributed time service, Ph.D. dissertation, Stanford University (1983).

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:
Management, Performance, Reliability