@online{Kuhn2018-gradient,
TITLE = {Optimal Gradient Clock Synchronization in Dynamic Networks (Version 3)},
AUTHOR = {Kuhn, Fabian and Lenzen, Christoph and Locher, Thomas and Oshman, Rotem},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1005.2894},
EPRINT = {1005.2894},
EPRINTTYPE = {arXiv},
YEAR = {2018},
ABSTRACT = {We study the problem of clock synchronization in highly dynamic networks,<br>where communication links can appear or disappear at any time. The nodes in the<br>network are equipped with hardware clocks, but the rate of the hardware clocks<br>can vary arbitrarily within specific bounds, and the estimates that nodes can<br>obtain about the clock values of other nodes are inherently inaccurate. Our<br>goal in this setting is to output a logical clock at each node such that the<br>logical clocks of any two nodes are not too far apart, and nodes that remain<br>close to each other in the network for a long time are better synchronized than<br>distant nodes. This property is called gradient clock synchronization.<br> Gradient clock synchronization has been widely studied in the static setting,<br>where the network topology does not change. We show that the asymptotically<br>optimal bounds obtained for the static case also apply to our highly dynamic<br>setting: if two nodes remain at distance $d$ from each other for sufficiently<br>long, it is possible to upper bound the difference between their clock values<br>by $O(d \log (D / d))$, where $D$ is the diameter of the network. This is known<br>to be optimal even for static networks. Furthermore, we show that our algorithm<br>has optimal stabilization time: when a path of length $d$ appears between two<br>nodes, the time required until the clock skew between the two nodes is reduced<br>to $O(d \log (D / d))$ is $O(D)$, which we prove to be optimal. Finally, the<br>techniques employed for the more intricate analysis of the algorithm for<br>dynamic graphs provide additional insights that are also of interest for the<br>static setting. In particular, we establish self-stabilization of the gradient<br>property within $O(D)$ time.<br>},
}