We present several solutions to the Firing Squad Synchronization Problem on grid networks of different shapes. The nodes are finite state processors that work in unison with other processors and in synchronized discrete steps. The networks we deal with are: the line, the ring and the square. For all of these models we consider one- and two-way communication modes and we also constrain the quantity of information that adjacent processors can exchange at each step. We first present synchronization algorithms that work in time , , , , where is a total number of processors. Synchronization methods are described through so called signals that are then used as building blocks to compose synchronization solutions for the cases that synchronization times are expressed by polynomials with nonnegative coefficients.
@article{ITA_2006__40_2_177_0, author = {Gruska, Jozef and Torre, Salvatore La and Napoli, Margherita and Parente, Mimmo}, title = {Different time solutions for the firing squad synchronization problem on basic grid networks}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {177--206}, publisher = {EDP-Sciences}, volume = {40}, number = {2}, year = {2006}, doi = {10.1051/ita:2006002}, mrnumber = {2252635}, zbl = {1112.68101}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2006002/} }
TY - JOUR AU - Gruska, Jozef AU - Torre, Salvatore La AU - Napoli, Margherita AU - Parente, Mimmo TI - Different time solutions for the firing squad synchronization problem on basic grid networks JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 177 EP - 206 VL - 40 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006002/ DO - 10.1051/ita:2006002 LA - en ID - ITA_2006__40_2_177_0 ER -
%0 Journal Article %A Gruska, Jozef %A Torre, Salvatore La %A Napoli, Margherita %A Parente, Mimmo %T Different time solutions for the firing squad synchronization problem on basic grid networks %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 177-206 %V 40 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006002/ %R 10.1051/ita:2006002 %G en %F ITA_2006__40_2_177_0
Gruska, Jozef; Torre, Salvatore La; Napoli, Margherita; Parente, Mimmo. Different time solutions for the firing squad synchronization problem on basic grid networks. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 40 (2006) no. 2, pp. 177-206. doi : 10.1051/ita:2006002. http://www.numdam.org/articles/10.1051/ita:2006002/
[1] An 8-states minimal time solution to the firing squad synchronization problem. Inform. Control 10 (1967) 22-42.
,[2] The Distributed Firing Squad Problem. SIAM J. Comput. 18 (1989) 990-1012. | Zbl
, , and ,[3] On Real Time Cellular Automata and Trellis Automata. Acta Inform 21 (1984) 393-407. | Zbl
and ,[4] Variations of the firing squad problem and applications. Inform. Process. Lett. 30 (1989) 153-157. | Zbl
,[5] A Minimal Time Solution of the Firing Squad Problem. Lect. Notes Appl. Math. Harvard University 298 (1962) 52-59.
,[6] Firing squad synchronization problem in reversible cellular automata. Theoret. Comput. Sci. 165 (1996) 475-482. | Zbl
and ,[7] Firing squad synchronization problem in number-conserving cellular automata, in Proc. of the IFIP Workshop on Cellular Automata, Santiago (Chile) (1998).
, and ,[8] The Firing Squad Synchronization Problem for Two Dimensional Arrays. Inform. Control 34 (1977) 153-157. | Zbl
,[9] On Time Optimal Solutions of the Firing Squad Synchronization Problem for Two-Dimensional Paths. Theoret. Comput. Sci. 259 (2001) 129-143. | Zbl
,[10] Optimal Time & Communication Solutions of Firing Squad Synchronization Problems on Square Arrays, Toruses and Rings, in Proc. of DLT'04. Lect. Notes Comput. Sci 3340 (2004) 200-211. Extended version at URL: http://www.dia.unisa.it/~parente/pub/dltExt.ps | Zbl
, and ,[11] Synchronization of 1-Way Connected Processors, in Proc. of the 11th International Symposium on Fundamentals of Computation Theory, FCT 1997, Krakow, Poland, September 1-3, 1997, edited by B. Chlebus and L. Czaja, Lect. Notes Comput. Sci. 1279 (1997) 293-304.
, and ,[12] Synchronization of a Line of Identical Processors at a Given Time. Fundamenta Informaticae 34 (1998) 103-128. | Zbl
, and ,[13] A Compositional Approach to Synchronize Two Dimensional Networks of Processors. Theoret. Inform. Appl. 34 (2000) 549-564. | Numdam | Zbl
, and ,[14] A six states minimal time solution to the firing squad synchronization problem. Theoret. Comput. Sci. 50 (1987) 183-238. | Zbl
,[15] On optimal solutions to the firing squad synchronization problem. Theoret. Comput. Sci. 168 (1996) 367-404. | MR | Zbl
,[16] A linear speed up theorem for cellular automata. Theoret. Comput. Sci. 101 (1992) 58-98. | Zbl
and ,[17] Signals in one dimensional cellular automata. Research Report N. 94-50, École Normale Supérieure de Lyon, France (1994).
and ,[18] Computation: Finite and Infinite Machines. Prentice-Hall (1967). | MR | Zbl
,[19] Sequential Machines, Selected Papers. Addison-Wesley, Reading, Mass, (1964). | Zbl
,[20] The Firing Squad Synchronization Problem for Graphs. Theoret. Comput. Sci. 14 (1981) 39-61. | Zbl
and ,[21] The Firing Squad Synchronization Problem on Cayley Graphs, in Proc. of the 20-th International Symposium on Mathematical Foundations of Computer Science MFCS'95, Prague, Czech Republic, 1995. Lect. Notes Comput. Sci. 969 (1995) 402-411.
,[22] Two and Three-Dimensional Firing Squad Synchronization Problems. Inform. Control 24 (1974) 163-180. | Zbl
,[23] An optimum solution to the firing squad synchronization problem. Inform. Control 9 (1966) 66-78. | Zbl
,Cited by Sources: