Summary
International Symposium on Nonlinear Theory and Its Applications
2016
Session Number:A4L-B
Session:
Number:A4L-B-3
An Implementation of Fault-Tolerant FSSP Algorithms
Naoki Kamikawa, Hiroshi Umeo,
pp.-
Publication Date:2016/11/27
Online ISSN:2188-5079
Summary:
We study a classical firing squad synchronization problem (FSSP) on a model of fault-tolerant cellular automata that might have possibly some defective cells. Several fault-tolerant nearly minimum-time FSSP algorithms are developed and implemented on finite-state automata. It is shown that, under some constraints on the distribution of defective cells, any cellular array of length $n$ with $p$ defective cell segments can be synchronized in $2n-2+p$ steps. The FSSP algorithms developed are realized on a finite state automaton with 164 states and 4792 rules.