Network Structure and the Firing Squad Synchronization problem

摘要

The firing squad synchronization problem, or fssp, requires that a network of automata, limited to finite memory and local communications only, cooperate in a global task. Previous solutions to the fssp usually assume a certain network topology. This paper presents embeddable solutions which exploit the existing network topology without relying on a priori assumptions. A uniform lower bound on the firing time of embeddable solutions is derived, and optimal embeddable solutions are presented for several classes of networks, including rings, star graphs, flower graphs, and n-dimensional rectangular arrays. In addition, we address the question, to what extent can solutions to the fssp for subnetworks contribute to the overall solution?