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

Abstract

top
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 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.

How to cite

top

Gruska, 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
  1. R. Balzer, An 8-states minimal time solution to the firing squad synchronization problem. Inform. Control10 (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.  
  3. C. Choffrut and K. Culik II, On Real Time Cellular Automata and Trellis Automata. Acta Inform21 (1984) 393–407.  
  4. K. Culik, Variations of the firing squad problem and applications. Inform. Process. Lett.30 (1989) 153–157.  
  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.  
  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. Control34 (1977) 153–157.  
  9. K. Kobayashi, On Time Optimal Solutions of the Firing Squad Synchronization Problem for Two-Dimensional Paths. Theoret. Comput. Sci.259 (2001) 129–143.  
  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. Sci3340 (2004) 200–211. Extended version at URL:  URIhttp://www.dia.unisa.it/~parente/pub/dltExt.ps
  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 Informaticae34 (1998) 103–128.  
  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.  
  14. J. Mazoyer, A six states minimal time solution to the firing squad synchronization problem. Theoret. Comput. Sci.50 (1987) 183–238.  
  15. J. Mazoyer, On optimal solutions to the firing squad synchronization problem. Theoret. Comput. Sci.168 (1996) 367-404.  
  16. J. Mazoyer and N. Reimen, A linear speed up theorem for cellular automata. Theoret. Comput. Sci.101 (1992) 58–98.  
  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).  
  19. E.F. Moore, Sequential Machines, Selected Papers. Addison-Wesley, Reading, Mass, (1964).  
  20. Y. Nishitani and N. Honda, The Firing Squad Synchronization Problem for Graphs. Theoret. Comput. Sci.14 (1981) 39–61.  
  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. Control24 (1974) 163–180.  
  23. A. Waksman, An optimum solution to the firing squad synchronization problem. Inform. Control9 (1966) 66–78.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.