A Class of Minimum-Time Minimum-State-Change Generalized FSSP Algorithms

Abstract

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 consider the FSSP from a view point of state-change-complexity that models the energy consumption of SRAM-type storage with which cellular automata might be built. In the present paper, we propose a class of minimum-time, minimum-state-change generalized FSSP (GFSSP, for short) algorithms for synchronizing any one-dimensional (1D) cellular automaton, where the synchronization operations are started from any cell in the array. We construct two minimum-time minimum-state-change GFSSP algorithms: one is based on Goto’s algorithm, known as the first minimum-time FSSP algorithm that is reconstructed again recently in Umeo et al. [13], and the other is based on Gerken’s one. These algorithms are optimum not only in time but also in state-change complexity.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

We study a synchronization problem that gives a finite-state protocol for synchronizing large-scale cellular automata. The synchronization in cellular automata has been known as a firing squad synchronization problem (FSSP) since its development, in which it was originally proposed by J. Myhill in Moore [6] to synchronize some/all parts of self-reproducing cellular automata. The problem has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed.

Here we consider the FSSP from a view point of state-change-complexity that models the energy consumption of SRAM-type storage with which cellular automata might be built. In the present paper, we propose a class of $n -2 + \max (k, n-k+1)$ minimum-time, $\varTheta$($n\log n$) minimum-state-change generalized FSSP (GFSSP, for short) algorithms for synchronizing any one-dimensional (1D) cellular automaton of length n, where the synchronization operations are started from any cell $k \ (1 \le k \le n)$ in the array. We construct two minimum-time minimum-state-change GFSSP algorithms, one is based on Goto’s algorithm, known as the first minimum-time FSSP algorithm that is reconstructed again recently in Umeo et al. [13], and the other is based on Gerken’s one. The Goto-based GFSSP algorithm is realized on a cellular automaton with 434 internal states and 13328 state-transition rules. The Gerken-based one is implemented on a cellular automaton with 215 internal states and 4077 state-transition rules. These algorithms are optimum not only in time but also in the state-change complexity. The implemented minimum-time GFSSP algorithms are the first ones having the minimum-state-change complexity.

In Sect. 2 we give a description of the 1D FSSP and review some basic results on FSSP and GFSSP algorithms. Section 3 gives new implementations and generalizations to the GFSSP algorithm having minimum-state-change complexity.

2 Firing Squad Synchronization Problem

2.1 Definition of Firing Squad Synchronization Problem

The firing squad synchronization problem (FSSP, for short) is formalized in terms of a model of cellular automata. Consider a 1D array of finite state automata. All cells (except the end cells) are identical finite state automata. The array operates in lock-step mode such that the next state of each cell (except the end cells) is determined by both its own present state and the present states of its right and left neighbors. All cells (soldiers), except one general cell, are initially in the quiescent state at time $t = 0$ and have the property whereby the next state of a quiescent cell having quiescent neighbors is the quiescent state. At time $t=0$ the general cell is in the fire-when-ready state, which is an initiation signal to the array. The FSSP is stated as follows: given an array of n identical cellular automata, including a general on the left end which is activated at time $t = 0$, we want to give the description (state set and next-state transition function) of the automata so that, at some future time, all of the cells will simultaneously and, for the first time, enter a special firing state. The initial general is on the left end of the array in the original FSSP.

Fig. 1.

A one-dimensional (1D) cellular automaton.

Figure 1 shows a finite 1D cellular array consisting of n cells, denoted by C$_{i}$, where $1 \le i \le n$. The set of states and the next-state transition function must be independent of n. Without loss of generality, we assume $n \ge 2$. The tricky part of the problem is that the same kind of soldiers having a fixed number of states must be synchronized, regardless of the length n of the array.

A formal definition of the FSSP is as follows: a cellular automaton $\mathcal {M}$ is a pair $\mathcal {M} =(\mathcal {Q}, \delta )$, where

• 1. $\mathcal {Q}$ is a finite set of states with three distinguished states G, Q, and F. G is an initial general state, Q is a quiescent state, and F is a firing state, respectively.

• 2. $\delta$ is a next state function such that $\delta : \mathcal {Q} \cup \{* \} \times \mathcal {Q} \times \mathcal {Q} \cup \{* \} \rightarrow \mathcal {Q}$. The state * $\notin \mathcal {Q}$ is a pseudo state of the border of the array.

• 3. The quiescent state Q must satisfy the following conditions: $\delta (\mathtt{Q}, \mathtt{Q}, \mathtt{Q}) = \delta (\mathtt{*}, \mathtt{Q}, \mathtt{Q}) = \delta (\mathtt{Q}, \mathtt{Q}, \mathtt{*}) = \mathtt{Q}$.

A cellular automaton $\mathcal {M}_{n}$ of length n, consisting of n copies of $\mathcal {M}$, is a 1D array whose positions are numbered from 1 to n. Each $\mathcal {M}$ is referred to as a cell and denoted by C$_{i}$, where $1 \le i \le n$. We denote a state of C$_{i}$ at time (step) t by S $^{t}_{i}$, where $t \ge 0, 1 \le i \le n$. A configuration of $\mathcal {M}_{n}$ at time t is a function $\mathcal {C}^{t}: [1, n] \rightarrow \mathcal {Q}$ and denoted as S $^{t}_{1}$ S $^{t}_{2}$ .... S $^{t}_{n}$. A computation of $\mathcal {M}_{n}$ is a sequence of configurations of $\mathcal {M}_{n}$, $\mathcal {C}^{0}$, $\mathcal {C}^{1}$, $\mathcal {C}^{2}$, ...., $\mathcal {C}^{t}$, ..., where $\mathcal {C}^{0}$ is a given initial configuration. The configuration at time $t+1$, $\mathcal {C}^{t+1}$, is computed by synchronous applications of the next transition function $\delta$ to each cell of $\mathcal {M}_{n}$ in $\mathcal {C}^{t}$ such that:

S $^{t+1}_{1}= \delta (\mathtt{*}, \mathtt{S}^{t}_{1}, \mathtt{S}^{t}_{2})$, S $^{t+1}_{i}= \delta (\mathtt{S}^{t}_{i-1}, \mathtt{S}^{t}_{i}, \mathtt{S}^{t}_{i+1})$, and S $^{t+1}_{n}= \delta (\mathtt{S}^{t}_{n-1}, \mathtt{S}^{t}_{n}, \mathtt{*})$.

A synchronized configuration of $\mathcal {M}_{n}$ at time t is a configuration $\mathcal {C}^{t}$, S $^{t}_{i}=\mathtt{F}$, for any $1 \le i \le n$.

The FSSP is to obtain an $\mathcal {M}$ such that, for any $n \ge 2$,

• 1. A synchronized configuration at time $t=T(n)$, $\mathcal {C}^{T(n)}= \overbrace{\mathtt{F}, \cdots , \mathtt{F}}^{n}$ can be computed from an initial configuration $\mathcal {C}^{0}= \mathtt{G}\overbrace{\mathtt{Q}, \cdots , \mathtt{Q}}^{n-1}$.

• 2. For any t, i such that $1 \le t \le T(n)-1$, $1 \le i \le n, \mathtt{S}^{t}_{i}\ne \mathtt{F}$.

The generalized FSSP (GFSSP) is to obtain an $\mathcal {M}$ such that, for any $n \ge 2$ and for any k such that $1 \le k \le n$,

• 1. A synchronized configuration at time $t=T(k, n)$, $\mathcal {C}^{T(k, n)}= \overbrace{\mathtt{F}, \cdots , \mathtt{F}}^{n}$ can be computed from an initial configuration $\mathcal {C}^{0}= \overbrace{\mathtt{Q}, \cdots , \mathtt{Q}}^{k-1}{} \mathtt{G}\overbrace{\mathtt{Q}, \cdots , \mathtt{Q}}^{n-k}$.

• 2. For any t, i, such that $1 \le t \le T(k, n)-1$, $1 \le i \le n, \mathtt{S}^{t}_{i}\ne \mathtt{F}$.

No cells fire before time $t=T(k, n)$. We say that $\mathcal {M}_{n}$ is synchronized at time $t=T(k, n)$ and the function T(k, n) is a time complexity for the synchronization.

2.2 Some Related Results on FSSP and GFSSP

Here we summarize some basic results on FSSP algorithms.

• Minimum-time FSSP algorithms with a general at one end

  The FSSP problem was first solved by J. McCarthy and M. Minsky who presented a 3n-step algorithm for n cells. In 1962, the first minimum-time, i.e. $(2n-2)$-step, synchronization algorithm was presented by Goto [3], with each cell having several thousands of states. Waksman [16] presented a 16-state minimum-time synchronization algorithm. Afterward, Balzer [1] and Gerken [2] developed an eight-state algorithm and a seven-state synchronization algorithm, respectively, thus decreasing the number of states required for the synchronization. In 1987, Mazoyer [4] developed a six-state synchronization algorithm which, at present, is the algorithm having the fewest states.

Theorem 1

(Goto [3], Waksman [16]) . There exists a cellular automaton that can synchronize any 1D array of length n in minimum $2n -2$ steps, where the general is located at a left (or right) end.

• Generalized minimum-time FSSP algorithms

  The generalized FSSP (GFSSP, for short) has also been studied, where an initial general can be located at any position in the array. The same kind of soldiers having a fixed number of states must be synchronized, regardless of the position k of the general and the length n of the array. Moore and Langdon [7] first studied the problem and presented a 17-state minimum-time GFSSP algorithm, i.e. operating in $n -2 +$max$(k, n-k+1)$ steps for n cells with the general on the kth cell from left end of the array. See Umeo et al. [12] for a survey on GFSSP algorithms and their implementations. Concerning the GFSSP, it has been shown impossible to synchronize any array of length n in less than $n -2 + \max (k, n-k+1)$ steps, where the general is located on C$_{k}$, $1 \le k \le n$.

Theorem 2

(Moore and Langdon [7] (Lower Bounds)) . The minimum-time in which the generalized firing squad synchronization could occur is no earlier than $n -2 + \max (k, n-k+1)$ steps, where the general is located on the kth cell from left end.

Theorem 3

(Umeo et al. [12]) . There exists an 8-state cellular automaton that can synchronize any 1D array of length n in minimum $n -2 + \max (k, n-k+1)$ steps, where the general is located on the kth cell from left end.

3 A Class of Minimum-Time, Minimum-State-Change GFSSP Algorithms

3.1 Designing Minimum-Time GFSSP Algorithms

In this section we develop a general methodology for designing a minimum-time GFSSP algorithm based on freezing-thawing technique. We can construct a minimum-time GFSSP algorithm from any minimum-time FSSP algorithm with a general at one end. The freezing-thawing technique developed in Umeo [10] enables us to have an FSSP algorithm with an arbitrary synchronization delay for 1D arrays. The freezing-thawing technique can be employed efficiently for the design of a minimum-time, minimum-state-change GFSSP algorithms in Sects. 3.3 and 3.4. The technique is described as follows:

Theorem 4

(Umeo [10]) . Let $t_{0}$, $t_{1}$, $t_{2}$ and $\varDelta t$ be any integer such that $t_{0} \ge 0$, $t_{1} = t_{0} + n-1$, $t_{1} \le t_{2}$ and $\varDelta t= t_{2} - t_{1}$. We assume that a usual synchronization operation is started at time $t= t_{0}$ by generating a special signal which acts as a general at the left end of 1D array of length n. We also assume that the right end cell of the array receives another special signals from outside at time $t_{1}=t_{0} + n-1$ and $t_{2}=t_{1} + \varDelta t$, respectively. Then, there exists a 1D cellular automaton that can synchronize the array of length n at time $t= t_{0} + 2n-2+\varDelta t$.

Fig. 2.

Space-time diagram for the construction of minimum-time GFSSP algorithm.

Consider a cellular array C$_{1}$, C$_{2}$, ..., C$_{n}$ of length n with an initial general on C$_{k}$, where $1 \le k \le n$. At time $t=0$ the general sends a unit speed (1 cell/1 step) signal to both ends. The cell C$_{k}$ keeps its state to indicate its initial position on the array. The signal reaches at the left and right ends at time $t=k-1$ and $t=n-k$, respectively, and generates a new general, denoted as G$_\mathrm{L}$ and G$_\mathrm{R}$ at each end. In Fig. 2, we illustrate a space-time diagram for the GFSSP construction. Each general, G$_\mathrm{L}$ and G$_\mathrm{R}$, starts minimum-time synchronization operations for the cellular space where the general is at its end by sending out a wake-up signal. At time $t=n-1$ the two signals collide with each other on the cell C$_{n-k+1}$ and the cellular space is divided into two parts by the collision. First, we consider the case where the initial general is in the left half of the given cellular space, i.e. $k \le n-k+1$. The wake-up signal generated by G$_\mathrm{L}$ reaches C$_{k}$ at time $t=2k-2$, then collides with the wake-up signal generated by G$_\mathrm{R}$. The larger part (left one in this case) is synchronized by a usual way, however, the small one is synchronized with time delay $\varDelta t = n-2k+1$. The wake-up signal for the larger part splits into two signals on C$_{k}$, one is an original wake-up signal and the other is a new slow signal which follows the wake-up signal at 1/2-speed. Note that the wake-up signal for the smaller part (right one in this case) never reaches C$_{k}$. As for the synchronization for the smaller part, a freezing-signal is generated at time $t_{1}= n-1$ on C$_{n-k+1}$ and the state configuration in the smaller part is frozen by the propagation of the 1/1-speed right-going freezing signal. At time $t_{2}= 2n-2k$, the split slow signal reaches C$_{n-k+1}$ and there a thawing signal is generated. The thawing signal thaws the frozen configuration progressively. Theorem 4 shows that the smaller part of length k is synchronized at time $t= 2n-k-1$. The larger part is also synchronized at time $t=2n-k-1$. Thus, the whole space can be synchronized at time $t=2n-k-1= n -2 + \max (k, n-k+1)$. Similar discussions can be made in the case where the initial general is in the right half of the cellular space. It is seen that any minimum-time FSSP algorithm with a general at one end can be embedded as a sub-algorithm for the synchronization of divided parts. A similar technique was used for solving FSSP with many generals in Schmid and Worsch [8]. Thus, we have:

Theorem 5

The schema given above can realize a minimum-time GFSSP algorithm by implementing two minimum-time FSSP algorithms with a general at one end.

Fig. 3.

An overview of the reconstructed Goto’s FSSP algorithm (left) and its snapshots on 32 cells of the 166-state, 4378-transition-rule implementation in Umeo et al. [13].

3.2 State-Change Complexity

Vollmar [15] introduced a state-change complexity in order to measure the efficiency of cellular automata, motivated by energy consumption in certain SRAM-type memory systems. The state-change complexity is defined as the sum of proper state changes of the cellular space during the computations. A formal definition is as follows: Consider an FSSP (GFSSP) algorithm operating on n cells. Let T(n) (resp., T(k, n)) be synchronization steps of the FSSP (GFSSP) algorithm. We define a matrix C of size $T(n)\times n$ (T(n) rows, n columns) (resp., $T(k, n) \times n$ (T(k, n) rows, n columns)) over $\{0, 1\}$, where each element $c_{i, j}$ on ith row, jth column of the matrix C is defined:

$$\begin{aligned} c_{i, j}={\left\{ \begin{array}{ll} 1 &{} \mathtt{S}^{j}_{i} \ne \mathtt{S}^{j-1}_{i}\\ 0 &{} otherwise. \end{array}\right. } \end{aligned}$$

(1)

The state-change complexity SC(n)(resp., $SC_{g}(n)$) of the FSSP (GFSSP) algorithm is the sum of 1’s elements in C defined as:

$$\begin{aligned} SC(n) = \displaystyle \sum _{j=1}^{T(n)}\sum _{i=1}^{n} c_{i, j}, \end{aligned}$$

(2)

$$\begin{aligned} SC_{g}(n) = \displaystyle 1/n\sum _{k=1}^{n}\sum _{j=1}^{T(k, n)}\sum _{i=1}^{n} c_{i, j}. \end{aligned}$$

(3)

Vollmar [15] showed that ${ \mathrm \Omega }(n \log n)$ state-changes are required for synchronizing n cells in $(2n-2)$ steps.

Theorem 6

(Vollmar [15]) . ${ \mathrm \Omega } (n \log n)$ state-change is necessary for synchronizing n cells in minimum-steps.

Gerken [2] presented a minimum-time, ${\Theta }(n \log n)$ minimum-state-change FSSP algorithm with a general at one end.

Theorem 7

(Gerken [2]) . $\mathrm{\Theta } (n \log n)$ state-change is sufficient for synchronizing n cells in $2n-2$ steps.

Goto’s algorithm (Goto [3]) has been known as the first minimum-time FSSP algorithm, however the paper itself has been a mysterious one for a long time due to its hard accessibility. Umeo [9] reconstructed the Goto’s algorithm and it is noted in Umeo [11] that the algorithm has ${ \mathrm \Theta } (n \log n)$ minimum-state-change complexity. Mazoyer [5] also reconstructed the algorithm again. Yunès [17] gave a new construction of Goto-like algorithms using the Wolfram’s rule 60. Recently, Umeo et al. [13] reconstructed the Goto’s algorithm again and realized it on a cellular automaton having 166-state and 4378 transition rules.

Theorem 8

(Umeo [11], Umeo et al. [13]) . The reconstructed Goto’s algorithm has ${ \mathrm \Theta } (n \log n)$ state-change complexity for synchronizing n cells in $2n-2$ steps.

In order to get a minimum-time, minimum-state-change GFSSP algorithm, we embed the reconstructed Goto’s algorithm and Gerken’s one with a general at one end. The state-change complexity in the right and left parts in Fig. 2 is $O((n-k+1)\log (n-k+1))$ and $O(k \log k)$, respectively, thus the total state-change-complexity of the constructed GFSSP algorithm is $O((n-k+1)\log (n-k+1))+O(k \log k) \le O(n \log n)$.

Thus, we have:

Theorem 9

There exists a minimum-time, minimum-state-change GFSSP algorithm.

Fig. 4.

Snapshots of configurations for Goto-based minimum-time, minimum-state-change GFSSP algorithm developed on $n=32$ cells with a general on C$_{7}$ (left) and C$_{20}$ (right), respectively.

3.3 An Implementation of Goto-Based Minimum-Time, Minimum-State-Change GFSSP Algorithm

The algorithm that Umeo [9] reconstructed is a non-recursive algorithm consisting of a marking phase and a 3n-step synchronization phase. In the first phase, by printing a special marker in the cellular space, the entire cellular space is divided into many smaller subspaces, each length of which increases exponentially with a common ratio of two, that is $2^{j}$, for any integer $j \ge 1$. The exponential marking is made by counting cells from both left and right ends of a given cellular space. In the second phase, each subspace is synchronized by starting a well-known conventional 3n-step synchronization algorithm from center point of each divided subspace. Figure 3 illustrates an overview of the reconstructed Goto’s algorithm. It can be seen that the overall algorithm does not call itself. Based on the reconstructed Goto’s algorithm, we realize a minimum-time, minimum-state-change GFSSP algorithm on a cellular automaton with 434 internal states and 13328 state-transition rules. Figure 4 shows some snapshots for the constructed GFSSP algorithm on 32 cells with a general on C$_{7}$ (left) and C$_{20}$ (right), respectively.

Fig. 5.

Space-time diagram of Gerken’s FSSP algorithm (left) and its snapshots on 37 cells.

Fig. 6.

Snapshots of configurations of Gerken-based minimum-time, minimum-state-change GFSSP algorithm developed on $n=34$ cells with a general on C$_{10}$ (left) and C$_{22}$ (right), respectively.

3.4 An Implementation of Gerken-Based Minimum-Time, Minimum-State-Change GFSSP Algorithm

Gerken [2] constructed a minimum-time 157-state FSSP algorithm and showed that the algorithm has a minimum-state-change complexity. The algorithm is the first one having the $\varTheta (n \log n)$ minimum-state-change complexity for synchronizing n cells with a general at one end. Figure 5 gives a space-time diagram for the algorithm (left) and some snapshots for the synchronization processes on 37 cells. Based on the algorithm, we realize a minimum-time, minimum-state-change GFSSP algorithm on a cellular automaton with 215 internal states and 4077 state-transition rules. Figure 6 shows some snapshots for the constructed GFSSP algorithm on 34 cells with a general on C$_{10}$ (left) and C$_{22}$ (right), respectively. Different snapshots can be found in Umeo et al. [14].

4 Summary

We studied the FSSP from a view point of state-change-complexity that models the energy consumption of SRAM-type storage with which cellular automata might be built. We have constructed two minimum-time minimum-state-change GFSSP algorithms: one is based on Goto’s algorithm, known as the first minimum-time FSSP algorithm, and the other is based on Gerken’s one. The Goto-based GFSSP algorithm is realized on a cellular automaton with 434 internal states and 13328 state-transition rules. The Gerken-based one is implemented on a cellular automaton with 215 internal states and 4077 state-transition rules. These algorithms are optimum not only in time but also in the state-change complexity. The implemented minimum-time GFSSP algorithms are the first ones having the minimum-state-change complexity.