Gradient Clock Synchronization with Practically Constant Local Skew

Abstract

Gradient Clock Synchronization (GCS) is the task of minimizing the local skew, i.e., the clock offset between neighboring clocks, in a larger network. While asymptotically optimal bounds are known, from a practical perspective they have crucial shortcomings:• Local skew bounds are determined by upper bounds on offset estimation that need to be guaranteed throughout the entire lifetime of the system.• Worst-case frequency deviations of local oscillators from their nominal rate are assumed, yet frequencies tend to be much more stable in the (relevant) short term.State-of-the-art deployed synchronization methods adapt to the true offset measurement and frequency errors, but achieve no nontrivial guarantees on the local skew.In this work, we provide a refined model and novel analysis of existing techniques for solving GCS in this model. By requiring only stability of measurement and frequency errors, we can circumvent existing lower bounds, leading to dramatic improvements under very general conditions. For example, if links exhibit a uniform worst-case estimation error of Δ and a change in estimation errors of δ ≪ Δ on relevant time scales, we bound the local skew by O( (Equation Presented ) D) for networks of diameter D, effectively "breaking"the established Ω(Δ log D) lower bound, which holds when δ = Δ. Surprisingly, these results require only very limited knowledge of Δ. In particular, the likely dominant term of O( (Equation Presented ) in the local skew is determined by the actual link performance, not an upper bound covering worst-case conditions.The full version of this paper [17] also shows how to achieve full self-stabilization, perform external synchronization, and limit the influence of local oscillators on δ to scale with the change of frequency of an individual oscillator on relevant time scales.