The synchronization in cellular automata has been known as the firing squad synchronization problem (FSSP) since its development, in which it was originally proposed by Myhill and reported by Moore in 1964 to synchronize all/some parts of self-reproducing cellular automata. The problem has been stu died extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed not only for one-dimensional (1D) arrays but also for multi-dimensional arrays. In the present paper, we construct a survey on the study of FSSP algorithms, focusing on recent developments.

Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The synchronization in cellular automata has been known as firing squad synchronization problem (FSSP) since its development. The FSSP has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we give a survey on recent developments in FSSP algorithms for two-dimensional rectangle cellular automata. Several state-efficient new implementations of synchronization algorithms are also given.

An existence or non-existence of five-state firing squad synchronization protocol has been a long-standing, famous open problem for a long time. In this paper, we answer partially to this problem by proposing a small five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n = 2 in 3n − 3 steps for any positive integer k.

We present an optimum bit-parallel/word-sequential systolic convolver. Our design is the best one among the previous many convolvers in the sense that its optimality in time and space performances is simultaneously attained without augmenting any global control, broadcasting, preloading, and/or multi sequential or parallel I/O ports, which were allowed in most of the previous designs. As an application of our convolver we give a systolic polynomial divider which can compute the polynomial division in exactly n + 0(1) steps on [min (n−m, m)/2] + 0(1) systolic cells, for the division of any degree n polynomial by any degree m polynomial(n ≧ m).