Synchronization modulo P in dynamic networks

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

Abstract

We define the mod P-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 P. We introduce an algorithm that achieves mod P-synchronization despite asynchronous starts in every dynamic network whose dynamic radius is bounded by some integer Δ, that is, there always exists a temporal path of length at most Δ from some fixed node γ, called a central node of the network, to all the other nodes. As opposed to the perfect synchronization achieved in the firing squad problem, mod P-synchronization thus does not require the network to be strongly connected. In our algorithm, all the nodes know Δ, but they ignore which nodes are central in the network. We also prove that if the bound Δ on the radious exists but is unknown, then mod P-synchronization is impossible.

All nodes in our algorithm fire in less than 6Pn rounds, where n is the number of nodes, after all nodes become active, but use unbounded counters. We then present a refinement of this algorithm so that memory usage becomes bounded while maintaining the same time complexity. The correctness of our first algorithm has been formally established in the proof assistant Isabelle.

Available as: PDF

Reference

@Article{penet:synchronization-tcs,
  author =       {Louis Penet de Monterno and Bernadette Charron-Bost and Stephan Merz},
  title =        {Synchronization modulo $P$ in dynamic networks},
  journal      = {Theoretical Computer Science},
  volume       = {942},
  pages        = {200-212},
  year         = {2023},
}