Self-Stabilizing Clock Synchronization with 1-bit Messages

Full versionInternational audienceWe study the fundamental problem of distributed clock synchronization in a basic probabilistic communication setting.We consider a synchronous fully-connected network of $n$ agents, where each agent has a local clock, that is, a counter increasing by one modulo $T$ in each round.The clocks have arbitrary values initially, and they must all indicate the same time eventually.We assume a pull communication model, where in every round each agent receives an $\ell$-bit message from a random agent.We devise several fast synchronization algorithms that use small messages and are self-stabilizing, that is,the complete initial state of each agent (not just its clock value) can be arbitrary.We first provide a surprising algorithm for synchronizing a binary clock ($T=2$) using $1$-bit messages ($\ell = 1$).This is a variant of the voter model and converges in $O(\log n)$ rounds w.h.p., unlike the voter model which needs polynomial time.Next we present an elegant extension of our algorithm that synchronizes a modulo $T=4$ clock, with $\ell = 1$, in $O(\log n)$ rounds.Using these two algorithms, we refine an algorithm of Boczkowski et al.~(SODA'17), that synchronizes a modulo $T$ clock in polylogarithmic time (in $n$ and $T$).The original algorithm uses $\ell=3$ bit messages, and each agent receives messages from two agents per round.Our algorithm reduces the message size to $\ell = 2$, and the number of messages received to one per round, without increasing the running time.Finally, we present two algorithms that simulate our last algorithm achieving $\ell < 2$, without hurting the asymptotic running time.The first algorithm uses a message space of size 3, i.e., $\ell =\log_2(3)$.The second requires a rough upper bound on $\log n$, and uses just 1-bit messages.More generally, our constructions can simulate any self-stabilizing algorithm that requires a shared clock, without increasing the message size and by only increasing the running time by a constant factor and a polylogarithmic term