Integrating external and internal clock synchronization

We address the problem of how to integrate fault-tolerant external and internal clock synchronization. In this paper we propose a new external/internal clock synchronization algorithm which provides both external and internal clock synchronization for as long as a majority of the reference time servers (servers with access to reference time) stay correct. When half or more of the reference time servers are faulty, the algorithm degrades to a fault-tolerant internal clock synchronization algorithm. We prove that at least 2F + 1 reference time servers are necessary for achieving external clock synchronization when up to F reference time servers can suffer arbitrary failures, thus the proposed algorithm provides maximum fault-tolerance. In this paper we also derive lower bounds for the best maximum external deviation achievable in standard mode and the best drift rate achievable in degraded mode. Our algorithm is optimal with respect to these two bounds: (1) the maximum external deviation is optimal in standard mode, and (2) the drift rate of the clocks is optimal in standard and degraded mode.