14/07/2020

Time- and space-optimal discrete clock synchronization in the beeping model

Michael Feldmann, Ardalan Khazraei, Christian Scheideler

Keywords: biological distributed algorithms, self-stabilization, distributed systems, beeping model, discrete clock synchronization

Abstract: 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 mod 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 [2] (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 Ω(maxT,n) rounds on the runtime and Ω(log(maxT,n)) bits of memory required for any such protocol. Afterwards we present a protocol that runs in O(maxT,n) rounds using at most O(log(maxT,n)) bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at SPAA 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers