# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Optimal Gradient Clock Synchronization in Dynamic Networks (Version 3)

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

1005.2894.pdf

(Preprint), 669KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Kuhn, F., Lenzen, C., Locher, T., & Oshman, R. (2018). Optimal Gradient Clock Synchronization in Dynamic Networks (Version 3). Retrieved from http://arxiv.org/abs/1005.2894.

Cite as: https://hdl.handle.net/21.11116/0000-0002-F1E8-8

##### Abstract

We study the problem of clock synchronization in highly dynamic networks,

where communication links can appear or disappear at any time. The nodes in the

network are equipped with hardware clocks, but the rate of the hardware clocks

can vary arbitrarily within specific bounds, and the estimates that nodes can

obtain about the clock values of other nodes are inherently inaccurate. Our

goal in this setting is to output a logical clock at each node such that the

logical clocks of any two nodes are not too far apart, and nodes that remain

close to each other in the network for a long time are better synchronized than

distant nodes. This property is called gradient clock synchronization.

Gradient clock synchronization has been widely studied in the static setting,

where the network topology does not change. We show that the asymptotically

optimal bounds obtained for the static case also apply to our highly dynamic

setting: if two nodes remain at distance $d$ from each other for sufficiently

long, it is possible to upper bound the difference between their clock values

by $O(d \log (D / d))$, where $D$ is the diameter of the network. This is known

to be optimal even for static networks. Furthermore, we show that our algorithm

has optimal stabilization time: when a path of length $d$ appears between two

nodes, the time required until the clock skew between the two nodes is reduced

to $O(d \log (D / d))$ is $O(D)$, which we prove to be optimal. Finally, the

techniques employed for the more intricate analysis of the algorithm for

dynamic graphs provide additional insights that are also of interest for the

static setting. In particular, we establish self-stabilization of the gradient

property within $O(D)$ time.

where communication links can appear or disappear at any time. The nodes in the

network are equipped with hardware clocks, but the rate of the hardware clocks

can vary arbitrarily within specific bounds, and the estimates that nodes can

obtain about the clock values of other nodes are inherently inaccurate. Our

goal in this setting is to output a logical clock at each node such that the

logical clocks of any two nodes are not too far apart, and nodes that remain

close to each other in the network for a long time are better synchronized than

distant nodes. This property is called gradient clock synchronization.

Gradient clock synchronization has been widely studied in the static setting,

where the network topology does not change. We show that the asymptotically

optimal bounds obtained for the static case also apply to our highly dynamic

setting: if two nodes remain at distance $d$ from each other for sufficiently

long, it is possible to upper bound the difference between their clock values

by $O(d \log (D / d))$, where $D$ is the diameter of the network. This is known

to be optimal even for static networks. Furthermore, we show that our algorithm

has optimal stabilization time: when a path of length $d$ appears between two

nodes, the time required until the clock skew between the two nodes is reduced

to $O(d \log (D / d))$ is $O(D)$, which we prove to be optimal. Finally, the

techniques employed for the more intricate analysis of the algorithm for

dynamic graphs provide additional insights that are also of interest for the

static setting. In particular, we establish self-stabilization of the gradient

property within $O(D)$ time.