DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2023.12

Self-Stabilizing Clock Synchronization in Probabilistic Networks

Authors: Bernadette Charron-Bost and Louis Penet de Monterno

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

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.

Cite as

Bernadette Charron-Bost and Louis Penet de Monterno. Self-Stabilizing Clock Synchronization in Probabilistic Networks. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.DISC.2023.12},
  URN =		{urn:nbn:de:0030-drops-191389},
  doi =		{10.4230/LIPIcs.DISC.2023.12},
  annote =	{Keywords: Self-stabilization, Clock synchronization, Probabilistic networks}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2022.28

Self-Stabilizing Clock Synchronization in Dynamic Networks

Authors: Bernadette Charron-Bost and Louis Penet de Monterno

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract

We consider the fundamental problem of periodic clock synchronization in a synchronous multi-agent system. Each agent holds a clock with an arbitrary initial value, and clocks must eventually be congruent, modulo some positive integer P. Previous algorithms worked in static networks with drastic connectivity properties and assumed that global informations are available at each node. In this paper, we propose a finite-state algorithm for time-varying topologies that does not require any global knowledge on the network. The only assumption is the existence of some integer D such that any two nodes can communicate in each sequence of D consecutive rounds, which extends the notion of strong connectivity in static network to dynamic communication patterns. The smallest such D is called the dynamic diameter of the network. If an upper bound on the diameter is provided, then our algorithm achieves synchronization within 3D rounds, whatever the value of the upper bound. Otherwise, using an adaptive mechanism, synchronization is achieved with little performance overhead. Our algorithm is parameterized by a function g, which can be tuned to favor either time or space complexity. Then, we explore a further relaxation of the connectivity requirement: our algorithm still works if there exists a positive integer R such that the network is rooted over each sequence of R consecutive rounds, and if eventually the set of roots is stable. In particular, it works in any rooted static network.

Cite as

Bernadette Charron-Bost and Louis Penet de Monterno. Self-Stabilizing Clock Synchronization in Dynamic Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.OPODIS.2022.28,
  author =	{Charron-Bost, Bernadette and Penet de Monterno, Louis},
  title =	{{Self-Stabilizing Clock Synchronization in Dynamic Networks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.28},
  URN =		{urn:nbn:de:0030-drops-176480},
  doi =		{10.4230/LIPIcs.OPODIS.2022.28},
  annote =	{Keywords: Self-stabilization, Clock synchronization, Dynamic networks}
}

Search Results

Documents authored by Penet de Monterno, Louis

Self-Stabilizing Clock Synchronization in Probabilistic Networks

Abstract

Cite as

Self-Stabilizing Clock Synchronization in Dynamic Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message