An Efficient Mapping Scheme for Embedding Any One-Dimensional Firing Squad Synchronization Algorithm onto Two-Dimensional Arrays
An Efficient Mapping Scheme for Embedding Any One-Dimensional Firing Squad Synchronization Algorithm onto Two-Dimensional Arrays
复制标题
将任意一维射击队同步算法嵌入二维数组的高效映射方案
DOI：
10.1007/3-540-45830-1_7
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Norio Fujiwara
中科院分区：
文献类型：
--
作者：
H. Umeo;Masashi Maeda;Norio Fujiwara
本文提出了一种将任意一维射击队同步算法嵌入到二维阵列上的有效映射方案，并基于该映射方案提出了几种新的二维同步算法。所提出的映射方案可以很容易地应用到设计的同步算法的容错性，算法操作的多维蜂窝阵列，并为一般的情况下，一般位于阵列上的任意位置。本文提出了一种六状态算法，可以在2（m+n）-4步内实现任意m × n矩形阵列的同步。此外，我们还提出了一种基于方阵的九状态最优时间同步算法。我们逐步减少每个元胞自动机的内部状态的数量在正方形和矩形阵列，实现9个国家的正方形阵列和6个国家的矩形阵列。这是迄今为止报道的用于同步矩形和正方形阵列的最小数量的状态。
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 anym×nrectangular 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.