Search

Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The synchronization in cellular automata, known as firing squad synchronization problem FSSP, has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed for not only one-dimensional but two-dimensional arrays. In the present paper, we propose a new recursive-halving based optimum-time synchronization algorithm that can synchronize any rectangle two-dimensional 2D arrays of size m ×n with a general at one corner in m+n+max m, n-3 steps. The algorithm proposed is quite different from previous designs and it can be easily generalized to 2D arrays with a general at any position of the array. The algorithm is isotropic concerning the side-lengths of 2D arrays and its correctness is transparent and easily verified.

The firing squad synchronization problem (FSSP) on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed. In the present paper, we focus our attention to two-dimensional square synchronizers that can synchronize square arrays and construct a survey on recent developments in their designs and implementations of optimum-time synchronization algorithms for square arrays. A new generalized square synchronization algorithm with an initial general at any position is also presented.

Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The firing squad synchronization problem (FSSP) on cellular automata (CA) has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed for not only one-dimensional but two-dimensional arrays. In the present paper, we study the FSSP on 1-bit-communication cellular automata, CA1-bit. The CA1-bit is a weakest subclass of CAs in which the amount of inter-cell communication bits transferred among neighboring cells at one step is restricted to 1-bit. We propose two state-efficient implementations of optimum-time FSSP algorithms for the CA1-bit and show that the communication restriction has no influence on the design of optimum-time FSSP algorithms. The implementations proposed are the smallest ones, known at present.

The firing squad synchronization problem on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed for not only one-dimensional arrays but two-dimensional arrays. In the present paper, we propose a new optimum-time synchronization algorithm that can synchronize any two-dimensional rectangle arrays of size m×n with a general at one corner in m+n+max(m, n)-3 steps. The algorithm is based on a simple recursive halving marking schema which helps synchronization operations on two-dimensional arrays. A proposed computer-assisted implementation of the algorithm gives a description of a two-dimensional cellular automaton in terms of a finite 384-state set and a local 112690- rule set.

The firing squad synchronization problem on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed for not only one-dimensional arrays but two-dimensional arrays. In the present paper, we propose a seven-state optimum-time synchronization algorithm that can synchronize any square arrays of size n × n with a general at one corner in 2n - 2 steps, which is a smallest realization of time-optimum square synchronizer known at present. The implementation is based on a new, simple zebra-like mapping scheme which embeds synchronization operations on one-dimensional arrays onto square arrays.

In recent years, interest in cellular automata (CA) has been increasing in the field of modeling real phenomena that occur in biology, chemistry, ecology, economy, geology, mechanical engineering, medicine, physics, sociology, and public transportation. Cellular automata are considered to provide a good model of complex systems in which an infinite array of finite state machines (cells) updates itself in a synchronous manner according to a uniform local rule. In the present paper, we study a problem solving on a special subclass of cellular automata: one-bit inter-cell communication cellular automaton. The problems dealt with are a firing squad synchronization problem, an integer sequence generation problem, an early bird problem, and a connectivity recognition problem for two-dimensional binary images, all of which are classical, fundamental problems that have been studied extensively on O(1)-bit communication models of cellular automata.

The Game of Life (GL), Larger Than Life (LtL), and the Kaleidoscope of Life (KL) are cellular automaton (CA) models with a rich palette of configurations, some of which facilitate universal computation. Common to all these models is that the transition rules by which they are governed are outer-totalistic. The KL distinguishes itself by the striking simplicity of its transition rule, which does not even take into account a cell's state itself for its update. This paper investigates an infinite class of CA, all of which are similar to KL except for their differently sized neighborhoods. Characterized by a discrete parameter d, a neighborhood in such a CA consists of the cells at Moore distances 1, 2,..., or dof a cell. We show that signal-carrying configurations ("gliders") occur in infinitely many of these CA models. We also show that the probability of convergence of a random configuration toward a dead cellular space increases with the increase in parameter d. These seemingly contradictory results suggest that the presence of gliders are not necessarily a reliable benchmark for the sustainability of Life in cellular space.

Though the regular and fixed structure of cellular automata greatly contributes to their simplicity, it imposes a strict limitation on the applications that can be modeled by them. This paper proposes swarm networks, a model in which cells, unlike in cellular automata, have irregular neighborhoods. Timed asynchronously, a cell in this model acts like an agentthat can dynamically interact with a varying set of other cells under the control of transition rules. The configurations in which cells are organized according to their neighborhoods can move around in space, following simple mechanical laws. We prove computational universality of this model by simulating a circuit consisting of asynchronously timed circuit modules. The proposed model may find applications in nanorobotic systems and artifical biological systems.

In this paper, we propose a new way to display alphabetical signs in order to write messages on a cellular phone in the Japanese language.

An efficient mapping scheme is proposed for embedding any one-dimensional firing squad synchronization algorithm onto 2-D arrays, and some new 2-D synchronization algorithms based on the mapping scheme are presented. The proposed mapping scheme can be readily applied to the design of synchronization algorithms with fault tolerance, algorithms operating on multi-dimensional cellular arrays, and for the generalized case where the general is located at an arbitrary position on the array. A six-state algorithm is developed that can synchronize any m × n rectangular array in 2(m + n) - 4 steps. In addition, we develop a nine-state optimum-time synchronization algorithm on square arrays. We progressively reduce the number of internal states of each cellular automaton on square and rectangular arrays, achieving nine states for a square array and six states for a rectangular array. These are the smallest number of states reported to date for synchronizing rectangular and square arrays.

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 smallest five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n = 2k in 3n-3 steps for any positive integer k. The number five is the smallest one known at present in the class of synchronization protocols proposed so far.

The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we propose a new optimum-time algorithm for synchronizing two-dimensional cellular automata. The algorithm can synchronize any rectangular array of size m × n in optimum m + n + max(m, n) - 3 steps.

In this paper, we study a trade-off between internal states and communication bits in firing squad synchronization protocols for k-bit communication-restricted cellular automata (CAk−bit) and propose several time-optimum state-efficient bit-transfer-based synchronization protocols It is shown that there exists a 1-state CA5−bit that can synchronize any n cells in 2n-2 optimum-step The result is interesting, since we know that there exists no 4-state synchronization algorithm on conventional O(1)-bit communication cellular automata A bit-transfer complexity is also introduced to measure the efficiency of synchronization protocols We show that Ω (n logn) bit-transfer is a lower-bound for synchronizing n cells in (2n-2) steps In addition, each optimum-time/non-optimum-time synchronization protocols, presented in this paper, has an O(n2) bit-transfer complexity, respectively.

In 1994, Yunes [19] began to explore 3n-step firing squad synchronization algorithms and developed two seven-state synchronization algorithms for one-dimensional cellular arrays His algorithms were so interesting in that he progressively decreased the number of internal states of each cellular automaton.In this paper, we propose a new symmetrical six-state 3n-step firing squad synchronization algorithm Our result improves the seven-state 3n-step synchronization algorithms developed by Yunes [19] The number six is the smallest one known at present in the class of 3n–step synchronization algorithms A non-trivial and new symmetrical six-state 3n-step generalized firing squad synchronization algorithm is also given In addition, we study a state-change complexity in 3n-step firing squad synchronization algorithms We show that our algorithms have O(n2) state-change complexity, on the other hand, the thread-like 3n-step algorithms developed so far have O(n logn) state-change complexity.

We propose several new generalized synchronization algorithms for 2-D cellular arrays. Firstly, a generalized linear-time synchronization algorithm and its 14-state implementation are given. It is shown that there exists a 14-state 2-D CA that can synchronize any m × n rectangular array in m + n + max(r + s , m + n – r – s + 2) – 4 steps with the general at an arbitrary initial position (r, s),where 1 ≤ r ≤ m, 1 ≤ s ≤ n. The generalized linear-time synchronization algorithm is interesting in that it includes an optimum-step synchronization algorithm as a special case where the general is located at one corner. In addition, we propose a noveloptimum-time generalized synchronization scheme that can synchronize any m × n array in m+n+max (m, n)− min (r, m−r+1)− min (s, n−s+1)−1 optimum steps.

The firing squad synchronization problem has been studied extensively for more than 40 years [1-18]. The present authors are involved in research on firing squad synchronization algorithms on two-dimensional (2-D) rectangular cellular arrays. Several synchronization algorithms on 2-D arrays have been proposed, including Beyer [2], Grasselli [3], Kobayashi [4], Shinahr [10], Szwerinski [12] and Umeo et al. [13, 15]. To date, the smallest number of cell states for which an optimum-time synchronization algorithm has been developed is 14 for rectangular array, achieved by Umeo et al. [15]. In the present paper, we propose a new optimum-time synchronization algorithm that can synchronize any 2-D m × n rectangular arrays in m + n + max(m, n) –3 steps. We progressively reduce the number of internal states of each cellular automaton on rectangular arrays, achieving twelve states. This is the smallest number of states reported to date for synchronizing rectangular arrays in optimum-step.

We present a survey and a comparison of the quantitative and qualitative aspects of the optimum-time synchronization algorithms developed thus far for one-dimensional cellular arrays. Several new results and viewpoints are also given.

We study a classical firing squad synchronization problem for a large sale of one- and two-dimensional cellular automata having 1-bit inter-cell communications (CA1-bit). First, it is shown that there exists a one-dimensional CA1-bit that can synchronize n cells with the general on the kth cell in n + max (k, n - k + 1) steps, where the performance is two steps larger than the optimum one that was developed for O(1)-bit communication model. Next, we give a two-dimensional CA1-bit which can synchronize any n × n square and m × n rectangular arrays in 2n - 1 and m + n + max (m, n) steps, respectively. Lastly, we propose a generalized synchronization algorithm that operates in m + n + max (r + s, m + n - r - s) + O(1) steps on two-dimensional m × n rectangular arrays with the general located at an arbitrary position (r, s) of the array, where 1 ≤ r ≤ m and 1 ≤ s ≤ n. The time complexities for the first three algorithms developed are one to four steps larger than optimum ones proposed for O(1)-bit communication models. We show that there still exist several new interesting synchronization algoritms on CA1-bit although more than 40 years have passed since the development of the problem.

It is shown that an infinite prime sequence can be generated in real-time by a cellular automaton having 1-bit inter-cell communications.

In this paper, we study a generalized synchronization problem for large scale cellular automata (CA) on one- and two- dimensional arrays. Some new generalized synchronization algorithms will be designed both on O(1)-bit and 1-bit inter-cell communication models of cellular automata. We give a 9-state and 13-state CA that can solve the generalized synchronization problem in optimum- and linear-time on O(1)-bit 1-D and 2-D CA, respectively. The number of internal states of the CA implemented is the smallest one known at present. In addition, it is shown that there exists a 1-bit inter-cell communication CA that can synchronize 1-D n cells with the general on the kth cell in n+max(k, n - k + 1) steps, which is two steps larger than the optimum time. We show that there still exist several new generalized synchronization algorithms, although more than 40 years have passed since the development of the problem.

This paper first presents a naive systolic algorithm for finding a closest point for each of n given points in linear time. Then, based on the algorithm, we propose linear time systolic algorithms for computing the visibility polygon and for trapezoidal partition or triangulation of a polygonal region which may contain holes. The visibility problem among n vertical line segments in the plane is also solved.