A Design of Symmetrical Six-State 3n-Step Firing Squad Synchronization Algorithms and Their Implementations
A Design of Symmetrical Six-State 3n-Step Firing Squad Synchronization Algorithms and Their Implementations
复制标题
对称六状态3n步射击班同步算法设计及其实现
DOI：
10.1007/11861201_21
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Kazuaki Hongyo
中科院分区：
文献类型：
--
作者：
H. Umeo;Masashi Maeda;Kazuaki Hongyo
1994年，Yunes[19]开始探索3n步行刑队同步算法，并开发了两种一维元胞阵列的七状态同步算法。他的算法非常有趣，因为他逐步减少了每个元胞自动机的内部状态数量。在本文中，我们提出了一种新的对称六状态3n步行刑队同步算法 我们的结果改进了 Yunes 开发的七状态 3n 步同步算法 [19] 数字 6 是目前已知的 3n 步同步算法中最小的一个 还给出了一种非平凡的新型对称六状态 3n 步广义行刑队同步算法 此外，我们研究了 3n 步行刑队中的状态变化复杂度 同步算法 我们证明我们的算法具有 O(n2) 状态更改复杂度，另一方面，迄今为止开发的类线程 3n 步算法具有 O(n logn) 状态更改复杂度。
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.