Synchronization Modulo k in Dynamic Networks

Louis Penet de Monterno, Bernadette Charron-Bost, Stephan Merz

Abstract

We define the mod k-synchronization problem as a weakening of the Firing Squad problem, where all nodes fire not at the same round, but at rounds that are all equal modulo k. We propose an algorithm that achieves mod k-synchronization in any dynamic network where there exist – possibly several – fixed spanning stars within each period of Δ consecutive rounds. In other words, we require that there always exists a temporal path of length at most Δ between some fixed node γ and every other node. As opposed to the perfect synchronization achieved in the Firing Squad problem, mod k-synchronization thus does not require any strong connectivity property in the network. In our algorithm, all the nodes know Δ, but they ignore what nodes are the centers of the spanning stars. We also prove that if the bound Δ for guaranteeing spanning stars exists but is unknown to the agents, then mod k-synchronization is impossible.

All nodes in our algorithm fire in less than 6kn + 4k rounds after all nodes become active, but unfortunately use unbounded counters. We then propose a refinement of this algorithm so that it becomes finite state while maintaining the same time complexity. The correctness of our first algorithm has been formally established in the proof assistant Isabelle.

Available as: PDF

This paper received the best paper award at SSS 2021.

Reference

@InProceedings{penet:synchronization-sss,
  author =       {Louis Penet de Monterno and Bernadette Charron-Bost and Stephan Merz},
  title =        {Synchronization Modulo $k$ in Dynamic Networks},
  booktitle = {23rd Intl. Symp. Stabilization, Safety, and Security of Distributed Systems (SSS 2021)},
  year =      2021,
  editor =    {Colette Johnen and Elad Michael Schiller and Stefan Schmid},
  volume =    13046,
  series =    {Lecture Notes in Computer Science},
  pages =     {425--439},
  address =   {Gothenburg, Sweden (online)},
  publisher = {Springer},
}