Different time solutions for the firing squad synchronization problem on basic grid networks
Gruska, Jozef ; Torre, Salvatore La ; Napoli, Margherita ; Parente, Mimmo
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006), p. 177-206 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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 n 2 , nlogn, nn, 2 n , where n 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.

Publié le : 2006-01-01
DOI : https://doi.org/10.1051/ita:2006002
Classification:  68Q80,  68Q10 
@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},
     volume = {40},
     year = {2006},
     pages = {177-206},
     doi = {10.1051/ita:2006002},
     mrnumber = {2252635},
     zbl = {1112.68101},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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, Tome 40 (2006) pp. 177-206. doi : 10.1051/ita:2006002. http://gdmltest.u-ga.fr/item/ITA_2006__40_2_177_0/

[1] R. Balzer, An 8-states minimal time solution to the firing squad synchronization problem. Inform. Control 10 (1967) 22-42.

[2] B.A. Coan, D. Dolev, C. Dwork and L. Stockmeyer, The Distributed Firing Squad Problem. SIAM J. Comput. 18 (1989) 990-1012. | Zbl 0679.68051

[3] C. Choffrut and K. Culik Ii, On Real Time Cellular Automata and Trellis Automata. Acta Inform 21 (1984) 393-407. | Zbl 0534.68039

[4] K. Culik, Variations of the firing squad problem and applications. Inform. Process. Lett. 30 (1989) 153-157. | Zbl 0665.68043

[5] E. Goto, A Minimal Time Solution of the Firing Squad Problem. Lect. Notes Appl. Math. Harvard University 298 (1962) 52-59.

[6] K. Imai and K. Morita, Firing squad synchronization problem in reversible cellular automata. Theoret. Comput. Sci. 165 (1996) 475-482. | Zbl 0872.68122

[7] K. Imai, K. Morita and K. Sako, Firing squad synchronization problem in number-conserving cellular automata, in Proc. of the IFIP Workshop on Cellular Automata, Santiago (Chile) (1998).

[8] K. Kobayashi, The Firing Squad Synchronization Problem for Two Dimensional Arrays. Inform. Control 34 (1977) 153-157. | Zbl 0364.94089

[9] K. Kobayashi, On Time Optimal Solutions of the Firing Squad Synchronization Problem for Two-Dimensional Paths. Theoret. Comput. Sci. 259 (2001) 129-143. | Zbl 0973.68157

[10] S. La Torre, J. Gruska and D. Parente, 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 1117.68443

[11] S. La Torre, M. Napoli and D. Parente, 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.

[12] S. La Torre, M. Napoli and D. Parente, Synchronization of a Line of Identical Processors at a Given Time. Fundamenta Informaticae 34 (1998) 103-128. | Zbl 0908.68005

[13] S. La Torre, M. Napoli and D. Parente, A Compositional Approach to Synchronize Two Dimensional Networks of Processors. Theoret. Inform. Appl. 34 (2000) 549-564. | Numdam | Zbl 0982.68092

[14] J. Mazoyer, A six states minimal time solution to the firing squad synchronization problem. Theoret. Comput. Sci. 50 (1987) 183-238. | Zbl 0635.68042

[15] J. Mazoyer, On optimal solutions to the firing squad synchronization problem. Theoret. Comput. Sci. 168 (1996) 367-404. | MR 1422963 | Zbl 0878.68088

[16] J. Mazoyer and N. Reimen, A linear speed up theorem for cellular automata. Theoret. Comput. Sci. 101 (1992) 58-98. | Zbl 0779.68063

[17] J. Mazoyer and V. Terrier, Signals in one dimensional cellular automata. Research Report N. 94-50, École Normale Supérieure de Lyon, France (1994).

[18] F. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1967). | MR 356580 | Zbl 0195.02402

[19] E.F. Moore, Sequential Machines, Selected Papers. Addison-Wesley, Reading, Mass, (1964). | Zbl 0147.24107

[20] Y. Nishitani and N. Honda, The Firing Squad Synchronization Problem for Graphs. Theoret. Comput. Sci. 14 (1981) 39-61. | Zbl 0454.68041

[21] Z. Roka, 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] I. Shinahr, Two and Three-Dimensional Firing Squad Synchronization Problems. Inform. Control 24 (1974) 163-180. | Zbl 0292.94039

[23] A. Waksman, An optimum solution to the firing squad synchronization problem. Inform. Control 9 (1966) 66-78. | Zbl 1111.68527