Different time solutions for the firing squad synchronization problem on basic grid networks

Gruska, Jozef; Torre, Salvatore La; Napoli, Margherita; Parente, Mimmo

doi:10.1051/ita:2006002

Gruska, Jozef ; Torre, Salvatore La ; Napoli, Margherita ; Parente, Mimmo

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 177-206.

Résumé

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}$ , $n log n$ , $n \sqrt{n}$ , $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.

EuDML MR Zbl

DOI : 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},
     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://archive.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://archive.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://archive.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, Tome 40 (2006) no. 2, pp. 177-206. doi : 10.1051/ita:2006002. http://archive.numdam.org/articles/10.1051/ita:2006002/

Bibliographie
Cité par

[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

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

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

[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

[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

[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

[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

[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

[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

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

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

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

[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 | Zbl

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

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

[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

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

Cité par Sources :