Implementations of FSSP Algorithms on Fault-Tolerant Cellular Arrays
| Autor: | Masashi Maeda, Hiroshi Umeo, Naoki Kamikawa, Gen Fujita |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Physics
Cellular array 010201 computation theory & mathematics Firing squad synchronization problem Rectangular array 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Fault tolerance 0102 computer and information sciences 02 engineering and technology 01 natural sciences Algorithm Cellular automaton |
| Zdroj: | Developments in Language Theory ISBN: 9783319986531 ACRI |
| DOI: | 10.1007/978-3-319-99813-8_25 |
| Popis: | The firing squad synchronization problem (FSSP, for short) on cellular automata has been studied extensively for more than fifty years, and a rich variety of FSSP algorithms has been proposed. Here we study the classical FSSP on a model of fault-tolerant cellular automata that might have possibly some defective cells and present the first state-efficient implementations of fault-tolerant FSSP algorithms for one-dimensional (1D) and two-dimensional (2D) arrays. It is shown that, under some constraints on the distribution and length of defective cells, any 1D cellular array of length n with p defective cell segments can be synchronized in \(2n-2+p\) steps and the algorithm is realized on a 1D cellular automaton with 164 states and 4792 transition rules. In addition, we give a smaller implementation for the 2D FSSP that can synchronize any 2D rectangular array of size \( m \times n\), including O(mn) rectangle-shaped isolated defective zones, exactly in \(2(m+n)-4\) steps on a cellular automaton with only 6 states and 939 transition rules. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|