Optimal time and communication solutions of FSSP on square arrays, toruses and rings

Investor logo

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GRUSKA Jozef LA TORRE Salvatore PARENTE Dominik

Year of publication 2004
Type Article in Periodical
Magazine / Source Lecture Notes in Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3340&spage=200
Field Informatics
Keywords Firing Squad Synchronization Problems
Description A new solution for the Firing Squad Synchronization Problem (FSSP) on two-dimensional square arrays is presented and its correctness is demonstrated in detail. Our new solution is time as well as communication optimal (the so-called minimal time 1-bit solution). In addition, it is shown that the technique developed and the results obtained allow also to solve in optimal time & communication FSSP for several other variants of this problem on networks shaped as square grids (with four Generals), square toruses and rings. This research has been completed while the first author was visiting the Dipartimento di Informatica ed Applicazioni, Universit degli Studi di Salerno. Work partially supported by MIUR grant ex-60% 2003 Universit di Salerno. The first author is also supported by the grant GAČR, 201/04/1153.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info