A Construction of Number-Conserving Firing Squad Synchronization Algorithm on One-Dimensional Arrays
We propose a number-conserving firing squad synchronization algorithm, which is nearly a timeoptimum solution to the firing squad synchronization problem (FSSP). The algorithm can be implemented on a number-conserving cellular automaton. In the numberconserving cellular automata (NCCA), any state of cells is represented by a single non-negative integer and total summed number of states in any configuration is conserved throughout its operations. The NC-CA can be thought as a model of the physical conservation law of mass or energy. Our synchronization algorithm has multiple firing states and can synchronize any array of length n in 2n — 1 steps.
cellular automaton firing squad synchronization algorithm number conserving cellular automata
Katsuhide Suzuki Hiroshi Umeo
Univ. of Osaka Electro-Communication,Neyagawa-shi, Hatsu-cho, 18-8,572-8530, Osaka, Japan
国际会议
黄山
英文
172-173
2010-05-28（万方平台首次上网日期，不代表论文的发表时间）