A Twelve-State Optimum-Time Synchronization Algorithm for Two-Dimensional Rectangular Cellular Arrays
A Twelve-State Optimum-Time Synchronization Algorithm for Two-Dimensional Rectangular Cellular Arrays
复制标题
二维矩形蜂窝阵列十二状态最优时间同步算法
DOI：
10.1007/11560319_20
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Akiguchi
中科院分区：
文献类型：
--
作者：
H. Umeo;Masaya Hisaoka;S. Akiguchi
行刑队同步问题已经被广泛研究了40多年[1-18]。本文主要研究二维矩形蜂窝阵列上的射击队同步算法。已经提出了几种二维阵列的同步算法，包括Beyer [2]，Grasselli [3]，小林[4]，Shinahr [10]，Szwerinski [12]和Umeo等人[13，15]。迄今为止，已开发的最佳时间同步算法的最小单元状态数是矩形阵列的14个，由Umeo等人实现。[15]。本文提出了一种新的最优时间同步算法，该算法可以在m + n + max（m，n）-3步内实现任意二维m × n矩形阵列的同步。我们逐步减少矩形阵列上每个元胞自动机的内部状态的数量，达到12个状态。这是迄今为止报道的最小数量的状态同步矩形阵列在最佳步骤。
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.