Session:

Multi-Agent Systems
Tuesday, March 02, 2004, 11.50 – 12.10

Session Chair:

Gulnara Baldoquín de la Peña

Paper Title:

Efficient 1-Bit-Communication Synchronization Protocols for Cellular Automata

Author(s):

Dr H.Umeo, University of Osaka Electro-Communication, Japan
Koshi Michisaka, Internet Initiative Japan Inc., Chiyoda-ku Kanda, Tokyo, Japan
Naoki Kamikawa, Noritsu Koki Co., Ltd., Wakayama, Japan
Jun Nishimura, MegaChips Co. LTD, Osaka, Japan

Abstract:

We study a classical firing squad synchronization problem for a large scale of one- and two-dimensional cellular automata having 1-bit inter-cell communications (CA). First, it is shown that there exists a one-dimensional CA that can synchronize n cells with the general on the left cell in optimum 2n -2 steps. In addition we show that there exists a one-dimensional CA that can synchronize n cells with the general on the k-th 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 CA which can synchronize any n x n square and m x 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 x 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 algorithms on CA, although more than 40 years have passed since the development of the problem.