×

An efficient solution of the firing mob problem. (English) Zbl 0745.68025

Summary: An 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.

MSC:

68M10 Network design and communication in computer systems
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Balzar, R., An 8-states minimal time solution to the firing squad synchronization problem, Inform. and control, 10, 22-42, (1967)
[2] Culik, K., Variations of the firing squad problem and applications, Inform. process. lett., 30, 153-157, (1989) · Zbl 0665.68043
[3] Culik, K.; Fris, I., Topological transformations as a tool in the design of systolic networks, Theoret. comput. sci., 37, 183-216, (1985) · Zbl 0584.68068
[4] Grefenstette, J.J., Network structure and the firing squad synchronization problem, J. comput. system sci., 26, 139-152, (1983) · Zbl 0512.68037
[5] Kobayashi, K., The firing squad synchronization problem for two dimensional arrays, Inform. and control, 34, 177-197, (1977) · Zbl 0364.94089
[6] Kobayashi, K., On the minimal firing time of the firing squad synchronization problem for poly-automata networks, Theoret. comput. sci., 7, 149-167, (1978) · Zbl 0397.68050
[7] Kobayashi, K., The firing squad synchronization problem for a class of polyautomata networks, J. comput. system sci., 17, 300-318, (1978) · Zbl 0392.68043
[8] Mazoyer, J., A six-state minimal time solution to the firing squad synchronization problem, Theoret. comput. sci., 50, 183-238, (1987) · Zbl 0635.68042
[9] Mazoyer, J., An overview of the firing squad synchronization problem, (), 82-94, Lecture Notes in Computer Science · Zbl 0656.68054
[10] Moore, F.R.; Langdon, G.G., A generalized firing squad problem, Inform. and control, 12, 212-220, (1968) · Zbl 0157.02202
[11] Romani, F., Cellular automata synchronization, Inform. sci., 10, 299-318, (1976) · Zbl 0334.94017
[12] Rosenstiehl, P.; Fiksel, J.R.; Holliger, A., Intelligent graphs: networks of finite automata capable of solving graph problem, () · Zbl 0265.94030
[13] Shinahr, I., Two- and three-dimensional firing squad synchronization problems, Inform. and control, 24, 163-180, (1974) · Zbl 0292.94039
[14] Waksman, A., An optimal solution to the firing squad synchronization problem, Inform. and control, 9, 66-78, (1966) · Zbl 1111.68527
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.