Information Technology Reference
In-Depth Information
4.3 Generalized Synchronization Algorithm on Rectangular Arrays
Now we consider a generalized firing squad synchronization problem, in which
the general can be initially located at any position on the array. Moore and
Langdon [14], Szwerinski [17] and Varshavsky, Marakhovsky and Peschansky
[22] developed optimum-time firing algorithms with 17, 10 and 10 internal
states, respectively. In these algorithms,
n
cells in a 1-D array are fired in
n −
2+max(
k, n − k
+ 1) steps, when the general is located at
C
k
. Our 2-D
mapping scheme can be applied to the design of synchronization algorithms
even in the generalized case. For any 2-D array
M
of size
m×n
with the general
at
C
r,s
, where 1
≤ r ≤ m
,1
≤ s ≤ n
, there exists a corresponding 1-D cellular
array
N
of length
m
+
n −
1 with the general at
C
r
+
s−
1
such that the config-
uration of
N
can be mapped on
M
, and
M
fires if and only if
N
fires. Based
on the 17-state generalized 1-D algorithm given by Moore and Langdon [14],
we obtain the following 2-D generalized synchronization algorithm that fires in
m
+
n −
1
−
2+max(
r
+
s −
1
,m
+
n − r − s
+ 1)=
m
+
n
+max(
r
+
s, m
+
n − r − s
+2)
−
4 steps. Two additional states are required in our construction
(details omitted). Szwerinski [17] also proposed an optimum-time generalized
2-D firing algorithm with 25,600 internal states that fires any
m × n
array in
m
+
n
+max(
m, n
)
−
min(
r, m− r
+1)
−
min(
s, n− s
+1)
−
1 steps, where (
r, s
)is
the general's initial position. Our 2-D generalized synchronization algorithm is
max(
r
+
s, m
+
n−r−s
+2)
−
max(
m, n
)+min(
r, m−r
+ 1)+min(
s, n−s
+1)
−
3
steps larger than the optimum algorithm proposed by Szwerinski [17]. However,
the number of internal states required to yield the firing condition is the smallest
known at present. Snapshots of our 19-state generalized synchronization algo-
rithm running on a rectangular array of size 6
×
8 with the general at
C
3
,
4
are
shown in Fig. 7.
[Theorem 7]
There exists a 19-state 2-D CA that can synchronize any
m × n
rectangular array in
m
+
n
+ max(
r
+
s, m
+
n − r − s
+2)
−
4 steps with the
general at an arbitrary initial position (
r, s
).
5 Implementation of Optimum-Time Synchronization
Algorithm on Square Arrays
In this section, we present a new 9-state synchronization algorithm that runs in
the optimum (2
n −
2) steps on
n × n
square arrays. Our algorithm is the same
as that of Shinahr [16] and operates as follows. By dividing the entire square
array into
n
L-shaped 1-D arrays such that the length of the
i
th L is 2
n−
2
i
+1
(1
≤ i ≤ n
), we treat the square firing as
n
independent 1-D firings with the
general located at the center cell. On the
i
th L, a general is generated at
C
i,i
at
time
t
=2
i −
2, and the general initiates the horizontal and vertical firings on
the row and column arrays via an optimum-time synchronization algorithm. The
array fires in optimum time
t
=2
i−
2+2(
n−i
+1)
−
2=2
n−
2. Let
Q
be a set of
internal states for the 1-D optimum-time synchronization algorithm. When we
implement the 1-D algorithm on 2-D square arrays based on the scheme above,
2
|| Q || −
1 states are normally required for independent row and column firings
when the firing state is shared.
