Clock Synchronization with Faults and Recoveries

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