# A Compositional Approach to Synchronize Two Dimensional Networks of Processors

Salvatore La Torre; Margherita Napoli; Mimmo Parente

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 6, page 549-564
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topLa Torre, Salvatore, Napoli, Margherita, and Parente, Mimmo. "A Compositional Approach to Synchronize Two Dimensional Networks of Processors." RAIRO - Theoretical Informatics and Applications 34.6 (2010): 549-564. <http://eudml.org/doc/222098>.

@article{LaTorre2010,

abstract = {
The problem of synchronizing a network
of identical processors that work synchronously
at discrete steps is studied. Processors are arranged as an array of
m rows and n columns and can exchange each other only one bit
of information.
We give algorithms which
synchronize square arrays of (n × n) processors and give some
general constructions to synchronize arrays of (m × n) processors.
Algorithms are given to synchronize in time n2, $n \lceil \log n\rceil$,
$n\lceil\sqrt n \rceil$ and 2n a square array of (n × n) processors.
Our approach is a modular description of
synchronizing algorithms in terms of "fragments" of cellular automata that are
called
signals.
Compositional rules to obtain new signals (and new synchronization
times) starting from known ones are given for an (m × n) array.
Using these compositional rules we construct
synchronizations in any "feasible" linear time and in any time expressed
by a polynomial with nonnegative coefficients.
},

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

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Cellular automata; synchronization.; cellular automata},

language = {eng},

month = {3},

number = {6},

pages = {549-564},

publisher = {EDP Sciences},

title = {A Compositional Approach to Synchronize Two Dimensional Networks of Processors},

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

volume = {34},

year = {2010},

}

TY - JOUR

AU - La Torre, Salvatore

AU - Napoli, Margherita

AU - Parente, Mimmo

TI - A Compositional Approach to Synchronize Two Dimensional Networks of Processors

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 6

SP - 549

EP - 564

AB -
The problem of synchronizing a network
of identical processors that work synchronously
at discrete steps is studied. Processors are arranged as an array of
m rows and n columns and can exchange each other only one bit
of information.
We give algorithms which
synchronize square arrays of (n × n) processors and give some
general constructions to synchronize arrays of (m × n) processors.
Algorithms are given to synchronize in time n2, $n \lceil \log n\rceil$,
$n\lceil\sqrt n \rceil$ and 2n a square array of (n × n) processors.
Our approach is a modular description of
synchronizing algorithms in terms of "fragments" of cellular automata that are
called
signals.
Compositional rules to obtain new signals (and new synchronization
times) starting from known ones are given for an (m × n) array.
Using these compositional rules we construct
synchronizations in any "feasible" linear time and in any time expressed
by a polynomial with nonnegative coefficients.

LA - eng

KW - Cellular automata; synchronization.; cellular automata

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

ER -

## References

top- R. Balzer, An 8-states minimal time solution to the firing squad synchronization problem. Inform. and Control10 (1967) 22-42. Zbl1347.68249
- K. Culik, Variations of the firing squad problem and applications. Inform. Process. Lett.30 (1989) 153-157. Zbl0665.68043
- 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. Kobayashy, The Firing Squad Synchronization Problem for Two Dimensional Arrays. Inform. and Control34 (1977) 153-157.
- K. Kobayashy, On Time Optimal Solutions of the Two-Dimensional Firing Squad Synchronization Problem, MFCS Workshop On Cellular Automata (1998).
- S. La Torre, M. Napoli and D. Parente, Synchronization of One-Way Connected Processors. Complex Systems10 (1996) 239-255. Zbl1010.68023
- S. La Torre, M. Napoli and D. Parente, Synchronization of a Line of Identical Processors at a Given Time. Fund. Inform.34 (1998) 103-128. Zbl0908.68005
- 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
- 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 Caley Graphs, in Proc. of MFCS'95. Prague, Czech Republic (1995). Lecture Notes in Comput. Sci.969 (1995) 402-411. Zbl1193.68170
- I. Shinair, Two and Three-Dimensional Firing Squad Synchronization Problems. Inform. and Control24 (1974) 163-180. Zbl0292.94039
- A. Waksman, An optimum solution to the firing squad synchronization problem. Inform. and Control9 (1966) 66-78. Zbl1111.68527

## Citations in EuDML Documents

top## NotesEmbed ?

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