{"ID":2846621,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.01420","arxiv_id":"2511.01420","title":"Gradient Clock Synchronization with Practically Constant Local Skew","abstract":"Gradient Clock Synchronization (GCS) is the task of minimizing the \\emph{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 non-trivial 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 \\emph{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 \\emph{change} in estimation errors of $δ\\ll Δ$ on relevant time scales, we bound the local skew by $O(Δ+δ\\log D)$ for networks of diameter $D$, effectively ``breaking'' the established $Ω(Δ\\log D)$ lower bound, which holds when $δ=Δ$. Similarly, we show how to limit the influence of local oscillators on $δ$ to scale with the \\emph{change} of frequency of an individual oscillator on relevant time scales. Moreover, we show how to ensure self-stabilization in this challenging setting. Last, but not least, we extend all of our results to the scenario of external synchronization, at the cost of a limited increase in stabilization time.","short_abstract":"Gradient Clock Synchronization (GCS) is the task of minimizing the \\emph{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...","url_abs":"https://arxiv.org/abs/2511.01420","url_pdf":"https://arxiv.org/pdf/2511.01420v2","authors":"[\"Christoph Lenzen\"]","published":"2025-11-03T10:13:12Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}