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

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

RAIRO - Theoretical Informatics and Applications (2006)

- Volume: 40, Issue: 2, page 177-206
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topGruska, Jozef, et al. "Different time solutions for the firing squad synchronization problem on basic grid networks." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 177-206. <http://eudml.org/doc/249723>.

@article{Gruska2006,

abstract = {
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 n2, nlogn, $n\sqrt n$,
2n, 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.
},

author = {Gruska, Jozef, La Torre, Salvatore, Napoli, Margherita, Parente, Mimmo},

journal = {RAIRO - Theoretical Informatics and Applications},

language = {eng},

month = {7},

number = {2},

pages = {177-206},

publisher = {EDP Sciences},

title = {Different time solutions for the firing squad synchronization problem on basic grid networks},

url = {http://eudml.org/doc/249723},

volume = {40},

year = {2006},

}

TY - JOUR

AU - Gruska, Jozef

AU - La Torre, Salvatore

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

DA - 2006/7//

PB - EDP Sciences

VL - 40

IS - 2

SP - 177

EP - 206

AB -
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 n2, nlogn, $n\sqrt n$,
2n, 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.

LA - eng

UR - http://eudml.org/doc/249723

ER -

## References

top- R. Balzer, An 8-states minimal time solution to the firing squad synchronization problem. Inform. Control10 (1967) 22–42.
- B.A. Coan, D. Dolev, C. Dwork and L. Stockmeyer, The Distributed Firing Squad Problem. SIAM J. Comput.18 (1989) 990–1012. Zbl0679.68051
- C. Choffrut and K. Culik II, On Real Time Cellular Automata and Trellis Automata. Acta Inform21 (1984) 393–407. Zbl0534.68039
- K. Culik, Variations of the firing squad problem and applications. Inform. Process. Lett.30 (1989) 153–157. Zbl0665.68043
- E. Goto, A Minimal Time Solution of the Firing Squad Problem. Lect. Notes Appl. Math. Harvard University 298 (1962) 52–59.
- K. Imai and K. Morita, Firing squad synchronization problem in reversible cellular automata. Theoret. Comput. Sci.165 (1996) 475–482. Zbl0872.68122
- 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). Zbl1011.68056
- K. Kobayashi, The Firing Squad Synchronization Problem for Two Dimensional Arrays. Inform. Control34 (1977) 153–157. Zbl0364.94089
- K. Kobayashi, On Time Optimal Solutions of the Firing Squad Synchronization Problem for Two-Dimensional Paths. Theoret. Comput. Sci.259 (2001) 129–143. Zbl0973.68157
- 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. Sci3340 (2004) 200–211. Extended version at URL: Zbl1117.68443URIhttp://www.dia.unisa.it/~parente/pub/dltExt.ps
- 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.
- S. La Torre, M. Napoli and D. Parente, Synchronization of a Line of Identical Processors at a Given Time. Fundamenta Informaticae34 (1998) 103–128. Zbl0908.68005
- 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. Zbl0982.68092
- J. Mazoyer, A six states minimal time solution to the firing squad synchronization problem. Theoret. Comput. Sci.50 (1987) 183–238. Zbl0635.68042
- J. Mazoyer, On optimal solutions to the firing squad synchronization problem. Theoret. Comput. Sci.168 (1996) 367-404. Zbl0878.68088
- J. Mazoyer and N. Reimen, A linear speed up theorem for cellular automata. Theoret. Comput. Sci.101 (1992) 58–98. Zbl0779.68063
- J. Mazoyer and V. Terrier, Signals in one dimensional cellular automata. Research Report N. 94–50, École Normale Supérieure de Lyon, France (1994). Zbl0915.68125
- F. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1967). Zbl0195.02402
- E.F. Moore, Sequential Machines, Selected Papers. Addison-Wesley, Reading, Mass, (1964). Zbl0147.24107
- Y. Nishitani and N. Honda, The Firing Squad Synchronization Problem for Graphs. Theoret. Comput. Sci.14 (1981) 39–61. Zbl0454.68041
- 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. Zbl1193.68170
- I. Shinahr, Two and Three-Dimensional Firing Squad Synchronization Problems. Inform. Control24 (1974) 163–180. Zbl0292.94039
- A. Waksman, An optimum solution to the firing squad synchronization problem. Inform. Control9 (1966) 66–78. Zbl1111.68527

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.