Synchronization modulo P in dynamic networks

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, nodes know Δ, but they ignore which nodes are central in the network. We also prove that if the bound Δ on the radius exists but is unknown, then mod P-synchronization is impossible. All nodes in our algorithm fire in less that 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.