Metraipolis › archive › dc_970e1c9175ca

Self-stabilising approximate clock synchronisation requires linear time — arXiv:2611.04725

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04725
License (as archived)
CC0-1.0
Archived
2026-11-04T21:45:42.583Z
SHA-256 of the archived text
f8f733175ff12fb1576cc1cc11b9b477d3072bccb6fc430a33cca65864565132
Stable URL of this page
https://metraipolis.com/documento/dc_970e1c9175ca

How to cite

Self-stabilising approximate clock synchronisation requires linear time — arXiv:2611.04725 — arXiv (en), https://arxiv.org/abs/2611.04725 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_970e1c9175ca (Metraipolis archive dc_970e1c9175ca, sha256 f8f733175ff12fb1576cc1cc11b9b477d3072bccb6fc430a33cca65864565132)
BibTeX
@misc{dc970e1c9175ca,
  title = {Self-stabilising approximate clock synchronisation requires linear time — arXiv:2611.04725},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04725},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_970e1c9175ca; sha256 f8f733175ff12fb1576cc1cc11b9b477d3072bccb6fc430a33cca65864565132},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04725. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $\Theta(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $\Omega(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2611.04725 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T21:36:19.384Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).