We consider networked systems in which each agent holds a certain variable, called clock, and study the synchronization problem: all clocks must eventually reach equal values modulo some given positive integer P, despite the arbitrary values of the clocks. We present some scenarios in which this problem is useful.
Agents communicate by exchanging messages and dynamic graphs are used to describe the time-varying communication graph. The connectivity in the network s captured by an integer, called “dynamic diameter”. We introduce the SAP algorithm, and prove that it solves the synchronization problem under the sole condition of a finite dynamic diameter. We examine its behavior when a bound on the dynamic diameter is known by the agents, and show that it still works when no bound is known by using an adaptive mechanism for clock periods, with a limited stabilization time overhead compared to the previous case.
In the last part, we stretch the class of networks in which the synchronization problem is solvable as much as possible: We introduce the class of strongly centered networks, and show that SAP also solves the synchronization problem in this class of dynamic networks. Then we exhibit scenarios suggesting that no further relaxation is possible.
