Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision

Abstract

In the Byzantine-tolerant clock synchronization problem, the goal is to synchronize the clocks of n fully connected nodes. The clocks run at rates between 1 and > 1, and messages have a delay (including computation) between d − U and d. Moreover, up to f < n/3 of the nodes can fail by deviating arbitrarily from the protocol, i.e., are Byzantine. Despite this interference, correct nodes need to generate distinguished events (or pulses) almost simultaneously and periodically. The quality of the solution is measured by the skew, which is the maximum real time difference between corresponding pulses. In the self-stabilizing setting, in addition we allow for transient failures, possibly of all nodes. Once transient faults have ceased and at most f nodes remain faulty, the system should start generating synchronized pulses again. We design a self-stabilizing solution to this problem with asymptotically optimal skew. We achieve our goal by refining and extending the protocol of Lynch and Welch and make the following contributions in the process.We give a simple analysis of the Lynch and Welch protocol with improved bounds on skew and tolerable difference in clock rates by rebuilding upon the main ingredient of their protocol, called approximate agreement.We give a modified version of the protocol so that the frequency and amount of communication between the nodes is reduced. The modification adds a step to adjust the clock rates by another application of approximate agreement. The skew bound achieved is asymptotically optimal for suitable choices of parameters.We present a method to add self-stabilization to the above protocols while preserving their skew bounds. The heart of the method is a coupling scheme that leverages a self-stabilizing protocol with a larger skew.