Abstract
We consider the fundamental problem of periodic clock synchronization in a synchronous multiagent 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 finitestate algorithm for timevarying 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.
BibTeX  Entry
@InProceedings{charronbost_et_al:LIPIcs.OPODIS.2022.28,
author = {CharronBost, Bernadette and Penet de Monterno, Louis},
title = {{SelfStabilizing Clock Synchronization in Dynamic Networks}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {28:128:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772655},
ISSN = {18688969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17648},
URN = {urn:nbn:de:0030drops176480},
doi = {10.4230/LIPIcs.OPODIS.2022.28},
annote = {Keywords: Selfstabilization, Clock synchronization, Dynamic networks}
}
Keywords: 

Selfstabilization, Clock synchronization, Dynamic networks 
Collection: 

26th International Conference on Principles of Distributed Systems (OPODIS 2022) 
Issue Date: 

2023 
Date of publication: 

15.02.2023 
Supplementary Material: 

Software (Source Code): https://gitlab.com/bossuet/sap_execution 