THE SYNCHRONIZATION OF NONUNIFORM NETWORKS OF FINITE AUTOMATA

The generalized firing squad synchronization problem (gfssp) is the well-known firing squad synchronization problem (fssp) extended to arbitrarily connected networks of finite automata. Here, the transmission delays associated with the links of a network are assumed to be 0; i.e., a signal can get through a link in no time. When the delays are allowed to be arbitrary nonnegative integers, the problem is called gfssp-nud (i.e., gfssp with nonuniform delays). We give for the first time a solution of gfssp-nud. The solution is independent of the structure of the network and the actual delays of the links. The firing time of the solution is bounded by O(Δ3+τmax), where τmax is the maximum transmission delay of any single link and Δ is the maximum transmission delay between the general and any other node of a given network. This answers an open question in Mazoyer (in "Automata Networks" (C. Choffrut, Ed.), pp. 82-93, Springer-Verlag, Berlin/New York, 1986). Our result is based on a strategy different from the one of Balzer and Waksman, which is used in almost all existing solutions of fssp and gfssp. The extension of gfssp and gfssp-nud to networks with more than one general is also considered. We show that (1) for any fixed k≥2, gfssp with at most k generals has a solution whose firing time is bounded by O(D), where D is the maximum distance between any two nodes of a given network, and gfssp-nud with at most k generals has a solution whose firing time is bounded by O((Φ+τmax)3), where Φ is the maximum transmission delay between any two nodes of a given network; (2) there are no solutions for gfssp and gfssp-nud with an arbitrary number of generals. © 1992.