License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.12
URN: urn:nbn:de:0030-drops-191389
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19138/
Go to the corresponding LIPIcs Volume Portal

Charron-Bost, Bernadette ; Penet de Monterno, Louis

Self-Stabilizing Clock Synchronization in Probabilistic Networks

pdf-format:
LIPIcs-DISC-2023-12.pdf (0.8 MB)

Abstract

We consider the fundamental problem of clock synchronization in a synchronous multi-agent system. Each agent holds a clock with an arbitrary initial value, and clocks must eventually indicate the same value, modulo some integer P. A known solution for this problem in dynamic networks is the self-stabilization SAP (for self-adaptive period) algorithm, which uses finite memory and relies solely on the assumption of a finite dynamic diameter in the communication network.
This paper extends the results on this algorithm to probabilistic communication networks: We introduce the concept of strong connectivity with high probability and we demonstrate that in any probabilistic communication network satisfying this hypothesis, the SAP algorithm synchronizes clocks with high probability. The proof of such a probabilistic hyperproperty is based on novel tools and relies on weak assumptions about the probabilistic communication network, making it applicable to a wide range of networks, including the classical push model. We provide an upper bound on time and space complexity.
Building upon previous works by Feige et al. and Pittel, the paper provides solvability results and evaluates the stabilization time and space complexity of SAP in two specific cases of communication topologies.

BibTeX - Entry

@InProceedings{charronbost_et_al:LIPIcs.DISC.2023.12,
  author =	{Charron-Bost, Bernadette and Penet de Monterno, Louis},
  title =	{{Self-Stabilizing Clock Synchronization in Probabilistic Networks}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19138},
  URN =		{urn:nbn:de:0030-drops-191389},
  doi =		{10.4230/LIPIcs.DISC.2023.12},
  annote =	{Keywords: Self-stabilization, Clock synchronization, Probabilistic networks}
}

Keywords: Self-stabilization, Clock synchronization, Probabilistic networks
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI