State-efficient realization of fault-tolerant FSSP algorithms

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) cellular arrays. It is shown that, under some constraints on the length and distribution 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 of length \(n, 2 \le n \le 50\), having 164 states and 4792 transition rules. In addition, we give by far a smaller-state implementation of a 2D FSSP algorithm that can synchronize any 2D rectangular array of size \(m \times n\), possibly including at most O(mn) isolated defective zones, exactly in \(2(m+n)-4\) steps on a cellular automaton with only 6 states and 935 transition rules.