Information Technology Reference
In-Depth Information
from the boundary encircling the array. The faulty regions can be regarded as
obstacles or holes in the array. To simplify the definition of a faulty region in our
construction, each faulty cell is assumed to be marked by a boundary symbol. A
typical 2-D rectangular array with 16 isolated holes (obstacles) is shown in Fig.
5. The problem is to design a firing squad synchronization algorithm such that
non-faulty cells on the array fire simultaneously. The algorithm given in The-
orem 4 can run without modification on any 2-D rectangular array containing
isolated rectangular holes. Snapshots of our 6-state fault-tolerant synchroniza-
tion algorithm running on a rectangular array of size 11
×
13 including 8 holes
are shown in Fig. 6.
Step:
12345678
1 Q Q Q Q Q Q Q Q
2 Q Q Q Q Q Q Q Q
3 Q Q Q P Q Q Q Q
4 Q Q Q Q Q Q Q Q
5 Q Q Q Q Q Q Q Q
6 Q Q Q Q Q Q Q Q
Step:
12345678
1 Q Q Q Q Q Q Q Q
2 Q Q Q
L
Q Q Q Q
3 Q Q
L D S
Q Q Q
4 Q Q Q
S
Q Q Q Q
5 Q Q Q Q Q Q Q Q
6 Q Q Q Q Q Q Q Q
Step:
12345678
1 Q Q Q
L
Q Q Q Q
2 Q Q
L
Q
D
Q Q Q
3 Q
L
Q
D
Q
S
Q Q
4 Q Q
D
Q
S
Q Q Q
5 Q Q Q
S
Q Q Q Q
6 Q Q Q Q Q Q Q Q
Step:
12345678
1 Q Q
L
Q
D1
Q Q Q
2 Q
L
Q Q
D D2
Q Q
3
L
Q Q
D
Q Q
S
Q
4 Q
D2 D
Q Q
S
Q Q
5 Q Q
D1
Q
S
Q Q Q
6 Q Q Q
S
Q Q Q Q
Step:
12345678
1 Q
L
Q Q Q
D
Q Q
2
L
Q Q Q
D
Q Q Q
3 Q Q Q
D
Q Q Q
S
4 Q Q
D
Q Q Q
S
Q
5 Q
D
Q Q Q
S
Q Q
6 Q Q Q Q
S
Q Q Q
Step:
12345678
1 K Q Q Q Q
D
Q Q
2 Q Q Q Q
D
Q Q Q
3 Q Q Q
D
Q Q Q Q
4 Q Q
D
Q Q Q Q
S
5
D2 D
Q Q Q Q
S
Q
6 Q
D1
Q Q Q
S
Q Q
Step:
12345678
1 K
I
Q Q Q
D
Q Q
2
I
Q Q Q
D
Q Q Q
3 Q Q Q
D
Q Q Q Q
4 Q Q
D
Q Q Q Q Q
5 Q
D
Q Q Q Q Q
S
6
D
Q Q Q Q Q
S
Q
Step:
12345678
1 K R
I
Q Q
D
Q Q
2 R
I
Q Q
D
Q Q Q
3
I
Q Q
D
Q Q Q Q
4 Q Q
D
Q Q Q Q Q
5 Q
D
Q Q Q Q Q Q
6
D
Q Q Q Q Q Q K
Step:
12345678
1 K
A
Q
I
Q
D
Q Q
2
A
Q
I
Q
D
Q Q Q
3 Q
I
Q
D
Q Q Q Q
4
I
Q
D
Q Q Q Q Q
5 Q
D
Q Q Q Q Q
G
6
D
Q Q Q Q Q
G
K
Step:
12345678
1
Step:1
12345678
1 K
A
R Q Q X Q Q
2
A
R Q Q X Q Q Q
3 R Q Q X Q Q Q
G
4 Q Q X Q Q Q
G
Q
5 Q X Q Q Q
G
Q
A
6 X Q Q Q
G
Q
A
K
Step:1
12345678
1 K R
B
Q Q
A
W Q
2 R
B
Q Q
A
W Q
G
3
B
Q Q
A
W Q
G
H
4 Q Q
A
W Q
G
H Q
5 Q
A
W Q
G
H Q
A
6
A
W Q
G
H Q
A
K
Step:12
12345678
1 K
A B
Q Q
A
R
G
2
A B
Q Q
A
R
G
Q
3
B
Q Q
A
R
G
Q Q
4 Q Q
A
R
G
Q Q H
5 Q
A
R
G
Q Q H
A
6
A
R
G
Q Q H
A
K
Step:1
12345678
1 K
A B
Q Q R K H
2
A B
Q Q R K H Q
3
B
Q Q R K H Q Q
4 Q Q R K H Q Q
B
5 Q R K H Q Q
B
H
6 R K H Q Q
B
H K
Step:1
12345678
1
Step:1
12345678
1 K
A B
R
G
H K R
2
A B
R
G
H K R
I
3
B
R
G
H K R
I
H
4 R
G
H K R
I
H
B
5
G
H K R
I
H
B A
6 H K R
I
H
B A
K
Step:1
12345678
1 K
A
Q K Q
A
K
A
2
A
Q K Q
A
K
A
Q
3 Q K Q
A
K
A
Q K
4 K Q
A
K
A
Q K Q
5 Q
A
K
A
Q K Q
A
6
A
K
A
Q K Q
A
K
Step:1
12345678
1 K
A G
K
I A
K
A
2
A G
K
I A
K
A G
3
G
K
I A
K
A G
K
4 K
I A
K
A G
K
I
5
I A
K
A G
K
I A
6
A
K
A G
K
I A
K
Step:1
12345678
1 K K K K K K K K
2 K K K K K K K K
3 K K K K K K K K
4 K K K K K K K K
5 K K K K K K K K
6 K K K K K K K K
Step:1
12345678
1
T T T T T T T T
K
A
Q R
I
D
Q Q
K
A B
Q R
G
K
I
2
A
Q R
I
D
Q Q Q
2
A B
Q R
G
K
I
H
2
T T T T T T T T
3 Q R
I
D
Q Q Q Q
3
B
Q R
G
K
I
H Q
3
T T T T T T T T
4
R
I
D
Q Q Q Q
G
4 Q R
G
K
I
H Q
B
4
T T T T T T T T
5
R
G
K
I
H Q
B A
5
T T T T T T T T
5
I
D
Q Q Q Q
G
H
6
G
K
I
H Q
B A
K
6
T T T T T T T T
6
D
Q Q Q Q
G
H K
Fig. 7.
Snapshots of our 19-state linear-time generalized firing squad synchronization
algorithm on rectangular arrays
[Theorem 5]
There exists a 6-state 2-D CA that can synchronize any
m × n
rectangular array containing isolated rectangular holes in 2(
m
+
n
)
−
4 steps.
4.2 Multi-dimensional Extension
Theorem 4 can be readily extended to multi-dimensional cases. For example, we
can give an extended theorem for three-dimensional (3-D) arrays.
[Theorem 6]
There exists a 6-state firing squad synchronization algorithm that
can synchronize any 3-D
m × n ×
solid arrays in 2(
m
+
n
+
)
−
6 steps.
