An efficient solution of the firing mob problem

AbstractAn efficient solution of the firing mob problem, which is the generalization of the well-known “firing squad synchronization” problem to finite bounded-degree networks, is presented. First, a method of synchronizing tree-connected networks is given. This method is extended to general networks. The total synchronization time is 3.5r where r is the radius of the network. No solution can work in time less than 3r on all networks. Moreover, it is shown why our solution will approach this value in the limit case when the number of states used becomes arbitrarily large