The firing squad synchronization problem on Cayley graphs

AbstractThe firing squad synchronization problem (FSSP for short) has been intensively studied in the one-dimensional space. The problem consists in the synchronization of a segment of automata. We generalize this problem on Cayley graphs. We give minimal time solutions for (a) synchronizing all cells in all minimal paths between any pair of cells of a Cayley graph; (b) synchronizing all cells in all minimal paths starting at a given cell G (the “general”) and leading to all cells at a given distance from G in a Cayley graph. In solutions for (b), in some cases, all cells of a ball in a Cayley graph will be synchronized, in other cases this is not possible because of the existence of “culs-de-sac”