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 metadatas

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-02987598
Contributor : George Giakkoupis <>
Submitted on : Wednesday, November 4, 2020 - 2:34:47 AM
Last modification on : Friday, November 6, 2020 - 3:10:20 AM

File

full.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02987598, version 1

Citation

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

Share

Metrics

Record views

68

Files downloads

105