The synchronization of nonuniform networks of finite automata

Publisher Website
Google Scholar
Abstract
The generalized firing squad synchronization problem (GFSSP) is the well-known firing squad synchronization problem extended to arbitrarily connected networks of finite automata. When the transmission delays associated with the links of a network are allowed to be arbitrary nonnegative integers, the problem is called GFSSP-NUD (GFSSP with nonuniform delays). A solution of GFSSP-NUD is given for the first time. 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( Delta /sup 3/+ tau /sub max/), where tau /sub max/ is the maximum transmission delay of any single link and Delta is the maximum transmission delay between the general and any other node of a given network. Extensions of GFSSP and GFSSP-NUD to networks with more than one general are presented.