Self-Stabilizing Clock Synchronization in Dynamic Networks

Authors Bernadette Charron-Bost, Louis Penet de Monterno



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.28.pdf
  • Filesize: 0.67 MB
  • 17 pages

Document Identifiers

Author Details

Bernadette Charron-Bost
  • DI ENS, École Normale Supérieure, 75005 Paris, France
Louis Penet de Monterno
  • École polytechnique, IP Paris, 91128 Palaiseau, France

Acknowledgements

We would like to thank Patrick Lambein-Monette, Stephan Merz, and Guillaume Prémel for very useful discussions. We are also indebted to Paolo Boldi and Sebastiano Vigna for their deep and inspiring work on self-stabilization.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.OPODIS.2022.28

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Self-stabilization
  • Clock synchronization
  • Dynamic networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Karine Altisen, Stéphane Devismes, Swan Dubois, and Franck Petit. Introduction to distributed self-stabilizing algorithms. Synthesis Lectures on Distributed Computing Theory, 8(1):1-165, 2019. Google Scholar
  2. D. Angluin, J. Aspnes, D. Eisenstat, and E. Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  3. A. Arora, S. Dolev, and M. Gouda. Maintaining digital clocks in step. Parallel Processing Letters, 1:11-18, 1991. Google Scholar
  4. P. Bastide, G. Giakkoupis, and H. Saribekyan. Self-stabilizing clock synchronization with 1-bit messages. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, 2021, pages 2154-2173. SIAM, 2021. Google Scholar
  5. M. Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the Second Symposium on Principles of Distributed Computing, pages 27-30, 1983. Google Scholar
  6. P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987. Google Scholar
  7. L. Boczkowski, A. Korman, and E. Natale. Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits. Distributed Comput., 32(3):173-191, 2019. Google Scholar
  8. P. Boldi and S. Vigna. Universal dynamic synchronous self-stabilization. Distributed Computing, 15(3):137-153, 2002. Google Scholar
  9. C. Boulinier, F. Petit, and V. Villain. Synchronous vs. asynchronous unison. Algorithmica, 51(1):61-80, 2008. Google Scholar
  10. B. Charron-Bost. Geometric bounds for convergence rates of averaging algorithms. Information and Computation, 2022. To appear, available at URL: https://arxiv.org/abs/2007.04837.
  11. B. Charron-Bost and A. Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49-71, 2009. Google Scholar
  12. A. Cornejo and F. Kuhn. Deploying wireless networks with beeps. In Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings, volume 6343 of Lecture Notes in Computer Science, pages 148-162. Springer, 2010. Google Scholar
  13. S. Dolev. Possible and impossible self-stabilizing digital clock synchronization in general graphs. Real Time Syst., 12(1):95-107, 1997. Google Scholar
  14. S. Dolev and J. L. Welch. Self-stabilizing clock synchronization in the presence of byzantine faults. J. ACM, 51(5):780-799, 2004. Google Scholar
  15. C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288-323, 1988. Google Scholar
  16. S. Even and S. Rajsbaum. Unison, canon, and sluggish clocks in networks controlled by a synchronizer. Math. Syst. Theory, 28(5):421-435, 1995. Google Scholar
  17. M. Feldmann, A. Khazraei, and C. Scheideler. Time- and space-optimal discrete clock synchronization in the beeping model. In SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, USA, 2020, pages 223-233. ACM, 2020. Google Scholar
  18. M. Gouda and T. Herman. Stabilizing unison. Inf. Process. Lett., 35(4):171-175, 1990. Google Scholar
  19. T. Herman and S. Ghosh. Stabilizing phase-clocks. Inf. Process. Lett., 54(5):259-265, 1995. Google Scholar
  20. A. Jadbabaie. Natural algorithms in a networked world: technical perspective. Commun. ACM, 55(12):100, 2012. Google Scholar
  21. Ronald Kempe, Joseph Y. Dobra, and Moshe Y. Gehrke. Gossip-based computation of aggregate information. In Proceeding of the 44th IEEE Symposium on Foundations of Computer Science, FOCS, pages 482-491, Cambridge, MA, USA, 2003. Google Scholar
  22. L. Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133-169, 1998. Google Scholar
  23. S. H. Strogatz. From kuramoto to crawford: exploring the onset of synchronization in populations of coupled oscillators. Physica D, 143(1-4):1-20, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail