Clock Synchronization with Faults and Recoveries
Boaz Barak, Shai Halevi, Amir Herzberg and Dalit Naor
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 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 at most 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 proactive secure mechanisms, which are also
designed to allow recovery from (arbitrary) faults. Therefore, our work
is crucial to realize these mechanisms securely.