Clock Synchronization with Faults and Recoveries

Authors: Boaz Barak, Shai Halevi, Amir Herzberg, and Dalit Naor.

Reference: Proceedings of the 19th annual ACM symposium on Principles of distributed computing (PODC 2000), pages 133-142. ACM, 2000.

Abstract: We present a convergence-function based clock synchronization algorithm, which is simple, efficient and fault-tolerant. The algorithm is tolerant of failures and allows recoveries, as long as less than a third of the processors are faulty `at the same time'. Arbitrary (Byzantine) faults are tolerated, without requiring awareness of failure or recovery. In contrast, previous clock synchronization algorithms limited the total number of faults throughout the execution, which is not realistic, or assumed fault detection.

The use of our algorithm ensures secure and reliable time services, a requirement of many distributed systems and algorithms. In particular, secure time is a fundamental assumption of {\em proactive secure} mechanisms, which are also designed to allow recovery from (arbitrary) faults. Therefore, our work is crucial to realize these mechanisms securely.

Keywords: Clock synchronization, Mobile adversary, Proactive systems

Availability: Paper available as Compressed PostScript (59 Kbyte).

Shai Halevi's home page.