Developments of Smallest Synchronization Protocols and Its Application to Multi-Dimensional Cellular Arrays

我们研究了一个行刑队同步问题（FSSP），给出了一个有限状态协议同步元胞自动机（CA）。在这个研究项目中，我们调查了更小的FSSP解决方案，不仅一维（1D），但多维CA。本文给出了一维CA的一类最小四态部分解。本文证明了二维方阵存在一个七态的方阵同步器，这是目前已知的方阵的最小解。我们还表明，存在一个九状态FSSP解决方案的二维矩形阵列。最后，我们提出了一类新的基于递归减半标记的最优时间多维FSSP算法。

We study a firing squad synchronization problem(FSSP) that gives a finite-state protocol for synchronizing cellular automata(CA). In this research project, we made an investigation into smaller FSSP solutions not only for one-dimensional(1D) but multi-dimensional CAs. We present a class of smallest 4-state partial solutions for 1D the CAs. It is shown that there exists a 7-state square synchronizer for 2D square arrays, which is a smallest solution for square arrays, known at present. We also show that there exists a nine-state FSSP solution for 2D rectangular arrays. In the last, we have proposed a new class of optimum-time multi-dimensional FSSP algorithms based on recursive-halving marking.