Paper Info
Title
A twelve-state optimum-time synchronization algorithm for two-dimensional rectangular cellular arrays
Abstract
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.
Year
DOI
Venue
2005
10.1007/11560319_20
UC
Keywords
Field
DocType
2-d array,new optimum-time synchronization algorithm,firing squad synchronization problem,two-dimensional rectangular cellular array,twelve-state optimum-time synchronization algorithm,n rectangular array,synchronization algorithm,squad synchronization algorithm,optimum-time synchronization algorithm,smallest number,rectangular cellular array,rectangular array,cellular automaton
Cellular automaton,Synchronization,Computer science,Firing squad synchronization problem,Time synchronization,Synchronizing,Algorithm,Synchronization algorithm,Rectangular array,Distributed computing
Conference
Volume
ISSN
ISBN
3699
0302-9743
3-540-29100-8
Citations 
PageRank 
References 
16
0.78
16
Authors
3
Name
Order
Citations
PageRank
Hiroshi Umeo136153.61
Masaya Hisaoka2724.26
Shunsuke Akiguchi3161.46