KIT | KIT-Bibliothek | Impressum | Datenschutz

A faster algorithm for the Birthday Song Singers Synchronization Problem (FSSP) in one-dimensional CA with multiple speeds

Worsch, Thomas 1
1 Karlsruher Institut für Technologie (KIT)


In cellular automata with multiple speeds for each cell i there is a positive integer p$_{i}$ such that this cell updates its state still periodically but only at times which are a multiple of p$_{i}$. Additionally there is a finite upper bound on all p$_{i}$. Manzoni and Umeo have described an algorithm for these (one-dimensional) cellular automata which solves the Firing Squad Synchronization Problem. This algorithm needs linear time (in the number of cells to be synchronized) but for many problem instances it is slower than the optimum time by some positive constant factor. In the present paper we derive lower bounds on possible synchronization times and describe an algorithm which is never slower and in some cases faster than the one by Manzoni and Umeo and which is close to a lower bound (up to a constant summand) in more cases.

Verlagsausgabe §
DOI: 10.5445/IR/1000136121
Veröffentlicht am 13.08.2021
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Informatik (INFORMATIK)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 08.2021
Sprache Englisch
Identifikator ISSN: 0001-5903, 1432-0525
KITopen-ID: 1000136121
Erschienen in Acta Informatica
Verlag Springer
Band 58
Heft 4
Seiten 451-462
Vorab online veröffentlicht am 19.07.2021
Nachgewiesen in Dimensions
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page