Skip to Main content Skip to Navigation
Conference papers

Self-Stabilizing Clock Synchronization with 1-bit Messages

Abstract : We 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : George Giakkoupis Connect in order to contact the contributor
Submitted on : Wednesday, November 4, 2020 - 2:34:47 AM
Last modification on : Tuesday, October 19, 2021 - 11:04:41 AM
Long-term archiving on: : Friday, February 5, 2021 - 6:12:22 PM


Files produced by the author(s)



Paul Bastide, George Giakkoupis, Hayk Saribekyan. Self-Stabilizing Clock Synchronization with 1-bit Messages. SODA 2021 - ACM-SIAM Symposium on Discrete Algorithms, Jan 2021, Alexandria, VA, United States. pp.1-27, ⟨10.1137/1.9781611976465.129⟩. ⟨hal-02987598⟩



Record views


Files downloads