Information Technology Reference
In-Depth Information
Step:0
12345678
Step:1
12345678
Step:2
12345678
Step:3
12345678
1
G1
L
L
L
L
L
L
L
1
A
C1
L
L
L
L
L
L
1
G1 B1
A
L
L
L
L
L
1
G1 C1 G1 G1
L
L
L
L
2
L
L
L
L
L
L
L
L
2
C2
L
L
L
L
L
L
L
2
B2 G1
L
L
L
L
L
L
2
C2
A
C1
L
L
L
L
L
3
L
L
L
L
L
L
L
L
3
L
L
L
L
L
L
L
L
3
A
L
L
L
L
L
L
L
3
G2 C2
L
L
L
L
L
L
4
L
L
L
L
L
L
L
L
4
L
L
L
L
L
L
L
L
4
L
L
L
L
L
L
L
L
4
G2
L
L
L
L
L
L
L
5
L
L
L
L
L
L
L
L
5
L
L
L
L
L
L
L
L
5
L
L
L
L
L
L
L
L
5
L
L
L
L
L
L
L
L
6
L
L
L
L
L
L
L
L
6
L
L
L
L
L
L
L
L
6
L
L
L
L
L
L
L
L
6
L
L
L
L
L
L
L
L
7
L
L
L
L
L
L
L
L
7
L
L
L
L
L
L
L
L
7
L
L
L
L
L
L
L
L
7
L
L
L
L
L
L
L
L
8
L
L
L
L
L
L
L
L
8
L
L
L
L
L
L
L
L
8
L
L
L
L
L
L
L
L
8
L
L
L
L
L
L
L
L
Step:4
12345678
Step:5
12345678
Step:6
Step:7
12345678
G1 B1
12345678
1
G1 B1
A
B1 C1
L
L
L
1
G1 C1 G1
L
C1
A
L
L
1
2
3
4
5
6
7
8
A
L
A
A
G1
L
1
G1 C1 G1
L
A
B1 B1
A
2
B2 G1 B1
A
L
L
L
L
2
C2 G1 C1 G1 G1
L
L
L
B2 G1 B1
A
B1 C1
L
L
2
C2 G1 C1 G1
L
C1
A
L
3
A
B2 G1
L
L
L
L
L
3
G2 C2
A
C1
L
L
L
L
A
B2 G1 B1
A
L
L
L
3
G2 C2 G1 C1 G1 G1
L
L
4
B2
A
L
L
L
L
L
L
4
L
G2 C2
L
L
L
L
L
L
A
B2 G1
L
L
L
L
4
L
G2 C2
A
C1
L
L
L
5
C2
L
L
L
L
L
L
L
5
C2 G2
L
L
L
L
L
L
A
B2
A
L
L
L
L
L
5
A
L
G2 C2
L
L
L
L
6
L
L
L
L
L
L
L
L
6
A
L
L
L
L
L
L
L
A
C2
L
L
L
L
L
L
6
B2 C2 G2
L
L
L
L
L
7
L
L
L
L
L
L
L
L
7
L
L
L
L
L
L
L
L
G2
L
L
L
L
L
L
L
7
B2
A
L
L
L
L
L
L
8
L
L
L
L
L
L
L
L
8
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
8
A
L
L
L
L
L
L
L
Step:8
12345678
Step:9
12345678
Step:10
12345678
Step:11
12345678
1
G1 B1
A
L
L
B1
A
C1
1
G1 C1 G1 G1
L
G1 C1 B1
1
G1 B1
A
B1
A
G1 B1
L
1
G1 C1 G1 B1 C1 G1 C1
L
2
B2 G1 B1
A
L
A
A
C1
2
C2 G1 C1 G1
L
A
C1 B1
2
B2 G1 B1
A
L
G1 B1
L
2
C2 G1 C1 G1 C1 G1 C1
L
3
A
B2 G1 B1
A
B1 C1
L
3
G2 C2 G1 C1 G1
L
C1 G1
3
A
B2 G1 B1
A
L
G1
A
3
G2 C2 G1 C1 G1 C1 G1 C1
4
L
A
B2 G1 B1
A
L
L
4
G2 G2 C2 G1 C1 G1 G1
L
4
B2
A
B2 G1 B1
A
B1
A
4
B2 G2 C2 G1 C1 G1 B1 C1
5
L
L
A
B2 G1
L
L
L
5
L
L
G2 C2
A
C1
L
L
5
A
L
A
B2 G1 B1
A
L
5
C2 C2 G2 C2 G1 C1 G1 C1
6
B2
A
B2
A
L
L
L
L
6
G2
A
L
G2 C2
L
L
L
6
G2 G2
L
A
B2 G1
L
L
6
G2 G2 C2 G2 C2
A
C1
L
7
A
A
C2
L
L
L
L
L
7
C2 C2 C2 G2
L
L
L
L
7
B2 B2 G2 B2
A
L
L
L
7
C2 C2 G2 B2 G2 C2
L
L
8
C2 C2
L
L
L
L
L
L
8
B2 B2 G2
L
L
L
L
L
8
L
L
A
A
L
L
L
L
8
L
L
C2 C2 C2
L
L
L
Step:12
12345678
Step:13
12345678
Step:14
12345678
1
G1 B1 G1 B1 G1 G1 B1 G1
1
G1 G1 G1 G1 G1 G1 G1 G1
1
F
F
F
F
F
F
F
F
2
B2 G1 B1 G1 B1 G1 B1 G1
2
G2 G1 G1 G1 G1 G1 G1 G1
2
F
F
F
F
F
F
F
F
3
G2 B2 G1 B1 G1 B1 G1 B1
3
G2 G2 G1 G1 G1 G1 G1 G1
3
F
F
F
F
F
F
F
F
4
B2 G2 B2 G1 B1 G1 B1 G1
4
G2 G2 G2 G1 G1 G1 G1 G1
4
F
F
F
F
F
F
F
F
5
G2 B2 G2 B2 G1 B1 G1 B1
5
G2 G2 G2 G2 G1 G1 G1 G1
5
F
F
F
F
F
F
F
F
6
G2 G2 B2 G2 B2 G1 B1 G1
6
G2 G2 G2 G2 G2 G1 G1 G1
6
F
F
F
F
F
F
F
F
7
B2 B2 G2 B2 G2 B2 G1
L
7
G2 G2 G2 G2 G2 G2
A
A
7
F
F
F
F
F
F
F
F
8
G2 G2 B2 G2 B2 G2
L
L
8
G2 G2 G2 G2 G2 G2
A
L
8
F
F
F
F
F
F
F
F
Fig. 8.
A configuration of a 9-state implementation of optimum-time firing on square
arrays
In our construction, by applying the Mazoyer's 6-state algorithm [10], we find
that 2 states can be deleted from the normal construction, rendering 9 states
su
;
cient for optimum-time square firing. We have tested our transition rule set
on squares of size 2
×
2 to 1000
×
1000. Figure 8 shows snapshots of configurations
of our 9-state synchronization algorithm running on a square of size 8
×
8. Thus
we have:
[Theorem 8]
There exists a 9-state 2-D CA that can synchronize any
n × n
square array in 2
n −
2 steps.
6 Conclusions
We have proposed a simple and e
;
cient mapping scheme for embedding any
1-D firing squad synchronization algorithm onto 2-D arrays and presented sev-
eral new 2-D synchronization algorithms. Although most of the algorithms are
slightly slower than the optimum algorithms, the number of internal states is
considerably smaller. Our mapping scheme can be readily applied to the de-
sign of synchronization algorithms with fault tolerance, algorithms operating
on multi-dimensional cellular arrays, and for the generalized case with the gen-
eral located at an arbitrary position in the array. The mapping scheme provides
the first fault-tolerant synchronization algorithm on 2-D arrays. In addition, we
