Time- and Space-Optimal Clock Synchronization in the Beeping Model
share
We consider the clock synchronization problem in the (discrete) beeping model: Given a network of n nodes with each node having a clock value δ(v) ∈{0,... T-1}, the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume arbitrary activations for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to {0,...,T-1}). We give an asymptotically optimal algorithm that runs in 4D + ⌊D/⌊ T/4 ⌋⌋· (T 4) = O(D) rounds, where D is the diameter of the network. Once all nodes are in sync, they beep at the same round every T rounds. The algorithm drastically improves on the O(T D)-bound of [ACGL'13] (where T is required to be at least 4n, so the bound is no better than O(nD)). Our algorithm is very simple as nodes only have to maintain 3 bits in addition to the ⌈log T ⌉ bits needed to maintain the clock. Furthermore we investigate the complexity of self-stabilizing solutions for the clock synchronization problem: We first show lower bounds of Ω(max{T,n}) rounds on the runtime and Ω(log(max{T,n})) bits of memory required for any such protocol. Afterwards we present a protocol that runs in O(max{T,n}) rounds using at most O(log(max{T,n})) bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.
READ FULL TEXT