An Efficient Mapping Scheme for Embedding Any One-Dimensional Firing Squad Synchronization Algorithm onto Two-Dimensional Arrays - Cellular Automata - page 76

Step:0 123456789 10111213
1 G L L L L L L L L L L L L
2 L L M M M M M L M L M L L
3 L L M M M M M L M L L L L
4 L L M M M M M L M L M M L
5 L L M M M M M L L L M M L
6 L L L L L L L L L L M M L
7 L M M M L M M M L L M M L
8 L M M M L M M M L L M M L
9 L M M M L L L L L L L L L
10 L M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:1 123456789 10111213
1 A C L L L L L L L L L L L
2 C L M M M M M L M L M L L
3 L L M M M M M L M L L L L
4 L L M M M M M L M L M M L
5 L L M M M M M L L L M M L
6 L L L L L L L L L L M M L
7 L M M M L M M M L L M M L
8 L M M M L M M M L L M M L
9 L M M M L L L L L L L L L
10 L M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:2 123456789 10111213
1 G B A L L L L L L L L L L
2 B A M M M M M L M L M L L
3 A L M M M M M L M L L L L
4 L L M M M M M L M L M M L
5 L L M M M M M L L L M M L
6 L L L L L L L L L L M M L
7 L M M M L M M M L L M M L
8 L M M M L M M M L L M M L
9 L M M M L L L L L L L L L
10 L M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:3 123456789 10111213
1 G C G G L L L L L L L L L
2 C G M M M M M L M L M L L
3 G G M M M M M L M L L L L
4 G L M M M M M L M L M M L
5 L L M M M M M L L L M M L
6 L L L L L L L L L L M M L
7 L M M M L M M M L L M M L
8 L M M M L M M M L L M M L
9 L M M M L L L L L L L L L
10 L M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:4 123456789 10111213
1 G B A B C L L L L L L L L
2 B A M M M M M L M L M L L
3 A B M M M M M L M L L L L
4 B C M M M M M L M L M M L
5 C L M M M M M L L L M M L
6 L L L L L L L L L L M M L
7 L M M M L M M M L L M M L
8 L M M M L M M M L L M M L
9 L M M M L L L L L L L L L
10 L M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:5 123456789 10111213
1 G C G L C A L L L L L L L
2 C G M M M M M L M L M L L
3 G L M M M M M L M L L L L
4 L C M M M M M L M L M M L
5 C A M M M M M L L L M M L
6 A L L L L L L L L L M M L
7 L M M M L M M M L L M M L
8 L M M M L M M M L L M M L
9 L M M M L L L L L L L L L
10 L M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:6 123456789 10111213
1 G B A L A A G L L L L L L
2 B A M M M M M L M L M L L
3 A L M M M M M L M L L L L
4 L A M M M M M L M L M M L
5 A A M M M M M L L L M M L
6 A G L L L L L L L L M M L
7 G M M M L M M M L L M M L
8 L M M M L M M M L L M M L
9 L M M M L L L L L L L L L
10 L M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:7 123456789 10111213
1 G C G L A B B C L L L L L
2 C G M M M M M L M L M L L
3 G L M M M M M L M L L L L
4 L A M M M M M L M L M M L
5 A B M M M M M L L L M M L
6 B B C L L L L L L L M M L
7 B M M M L M M M L L M M L
8 C M M M L M M M L L M M L
9 L M M M L L L L L L L L L
10 L M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:8 123456789 10111213
1

Step:9 123456789 10111213
1 G C G G L L C A A G L L L
2 C G M M M M M A M L M L L
3 G G M M M M M G M L L L L
4 G L M M M M M L M L M M L
5 L L M M M M M L L L M M L
6 L C A A G L L L L L M M L
7 C M M M L M M M L L M M L
8 A M M M L M M M L L M M L
9 A M M M L L L L L L L L L
10 G M M M L M M L M M M L L
11 L L L L L L L L L L L L L
Step:1 123456789 10111213
1 G B A B C L A A B B C L L
2 B A M M M M M B M C M L L
3 A B M M M M M B M L L L L
4 B C M M M M M C M L M M L
5 C L M M M M M L L L M M L
6 L A A B B C L L L L M M L
7 A M M M C M M M L L M M L
8 A M M M L M M M L L M M L
9 B M M M L L L L L L L L L
10 B M M M L M M L M M M L L
11 C L L L L L L L L L L L L
Step:1 123456789 10111213
1 G C G L C L A B B C C A L
2 C G M M M M M B M C M L L
3 G L M M M M M C M A L L L
4 L C M M M M M C M L M M L
5 C L M M M M M A L L M M L
6 L A B B C C A L L L M M L
7 A M M M C M M M L L M M L
8 B M M M A M M M L L M M L
9 B M M M L L L L L L L L L
10 C M M M L M M L M M M L L
11 C A L L L L L L L L L L L
Step:1 123456789 10111213
1 G B A L C L L B C C A A G
2 B A M M M M M C M A M G L
3 A L M M M M M C M A G L L
4 L C M M M M M A M G M M L
5 C L M M M M M A G L M M L
6 L L B C C A A G L L M M L
7 L M M M A M M M L L M M L
8 B M M M A M M M L L M M L
9 C M M M G L L L L L L L L
10 C M M M L M M L M M M L L
11 A A G L L L L L L L L L L
Step:1 123456789 10111213
1 G C G L C A L L C A A B B
2 C G M M M M M C M A M B C
3 G L M M M M M A M B B C L
4 L C M M M M M A M B M M L
5 C A M M M M M B B C M M L
6 A L L C A A B B C L M M L
7 L M M M A M M M L L M M L
8 L M M M B M M M L L M M L
9 C M M M B C L L L L L L L
10 A M M M C M M L M M M L L
11 A B B C L L L L L L L L L
Step:1 123456789 10111213
1 G B A L A A G L A A B B C
2 B A M M M M M A M B M C C
3 A L M M M M M A M B C C A
4 L A M M M M M B M C M M L
5 A A M M M M M B C C M M L
6 A G L A A B B C C A M M L
7 G M M M B M M M A L M M L
8 L M M M B M M M L L M M L
9 A M M M C C A L L L L L L
10 A M M M C M M L M M M L L
11 B B C C A L L L L L L L L
Step:1 123456789 10111213
1 G C G L A B B L A B B C C
2 C G M M M M M A M B M C A
3 G L M M M M M B M C C A A
4 L A M M M M M B M C M M G
5 A B M M M M M C C A M M L
6 B B L A B B C C A A M M L
7 B M M M B M M M A G M M L
8 L M M M C M M M G L M M L
9 A M M M C A A G L L L L L
10 B M M M A M M L M M M L L
11 B C C A A G L L L L L L L
Step:1 123456789 10111213
1 G B A L L B G L L B C C A
2 B A M M M M M L M C M A A
3 A L M M M M M B M C A A B
4 L L M M M M M C M A M M B
5 L B M M M M M C A A M M C
6 B G L L B C C A A B M M L
7 G M M M C M M M B B M M L
8 L M M M C M M M B C M M L
9 L M M M A A B B C L L L L
10 B M M M A M M C M M M L L
11 C C A A B B C L L L L L L
Step:1 123456789 10111213
1

Step:1 123456789 10111213
1 G B A B L B C C A L A A B
2 B A M M M M M A M A M B B
3 A B M M M M M L M A B B C
4 B L M M M M M A M B M M C
5 L B M M M M M A B B M M A
6 B C C A L A A B B C M M A
7 C M M M A M M M C C M M G
8 C M M M A M M M C A M M L
9 A M M M B B C C A A G L L
10 L M M M B M M A M M M L L
11 A A B B C C A A G L L L L
Step:1 123456789 10111213
1 G C G G L L C A A L A B B
2 C G M M M M M A M A M B C
3 G G M M M M M L M B B C C
4 G L M M M M M A M B M M A
5 L L M M M M M B B C M M A
6 L C A A L A B B C C M M B
7 C M M M A M M M C A M M B
8 A M M M B M M M A A M M C
9 A M M M B C C A A B B C L
10 L M M M C M M A M M M L L
11 A B B C C A A B B C L L L
Step:2 123456789 10111213
1 G B A B C L A A A L L B C
2 B A M M M M M A M L M C C
3 A B M M M M M L M B C C A
4 B C M M M M M L M C M M A
5 C L M M M M M B C C M M B
6 L A A A L L B C C A M M B
7 A M M M L M M M A A M M C
8 A M M M B M M M A B M M C
9 A M M M C C A A B B C C A
10 L M M M C M M B M M M A L
11 L B C C A A B B C C A L L
Step:2 123456789 10111213
1 G C G L C L A A A G L L C
2 C G M M M M M A M L M C A
3 G L M M M M M G M L C A A
4 L C M M M M M L M C M M B
5 C L M M M M M L C A M M B
6 L A A A G L L C A A M M C
7 A M M M L M M M A B M M C
8 A M M M L M M M B B M M A
9 A M M M C A A B B C C A A
10 G M M M A M M B M M M A G
11 L L C A A B B C C A A G L
Step:2 123456789 10111213
1 G B A L C L A A B B C L A
2 B A M M M M M B M C M A A
3 A L M M M M M B M L A A B
4 L C M M M M M C M A M M B
5 C L M M M M M L A A M M C
6 L A A B B C L A A B M M C
7 A M M M C M M M B B M M A
8 A M M M L M M M B C M M A
9 B M M M A A B B C C A A B
10 B M M M A M M C M M M B B
11 C L A A B B C C A A B B A
Step:2 123456789 10111213
1 G C G L C L A B B C C L A
2 C G M M M M M B M C M A B
3 G L M M M M M C M L A B B
4 L C M M M M M C M A M M C
5 C L M M M M M L A B M M C
6 L A B B C C L A B B M M A
7 A M M M C M M M B C M M A
8 B M M M L M M M C C M M B
9 B M M M A B B C C A A B B
10 C M M M B M M C M M M B A
11 C L A B B C C A A B B A C
Step:2 123456789 10111213
1 G B A L C L L B C C C L L
2 B A M M M M M C M C M L B
3 A L M M M M M C M L L B C
4 L C M M M M M C M L M M C
5 C L M M M M M L L B M M A
6 L L B C C C L L B C M M A
7 L M M M C M M M C C M M B
8 B M M M L M M M C A M M B
9 C M M M L B C C A A B B A
10 C M M M B M M A M M M A C
11 C L L B C C A A B B A C B
Step:2 123456789 10111213
1 G C G L C A L L C C C A L
2 C G M M M M M C M C M L L
3 G L M M M M M C M A L L C
4 L C M M M M M C M L M M A
5 C A M M M M M A L L M M A
6 A L L C C C A L L C M M B
7 L M M M C M M M C A M M B
8 L M M M A M M M A A M M A
9 C M M M L L C A A B B A C
10 C M M M L M M A M M M C B
11 C A L L C A A B B A C B L
Step:2 123456789 10111213
1

Step:2 123456789 10111213
1 G C G L A B B L C A A B B
2 C G M M M M M C M A M B L
3 G L M M M M M A M B B L A
4 L A M M M M M A M B M M B
5 A B M M M M M B B L M M B
6 B B L C A A B B L A M M A
7 B M M M A M M M A B M M C
8 L M M M B M M M B B M M B
9 C M M M B L A B B A C B L
10 A M M M L M M B M M M L L
11 A B B L A B B A C B L L L
Step:2 123456789 10111213
1 G B A L L B G L A A B B G
2 B A M M M M M A M B M G L
3 A L M M M M M A M B G L L
4 L L M M M M M B M G M M B
5 L B M M M M M B G L M M A
6 B G L A A B B G L L M M C
7 G M M M B M M M L B M M B
8 L M M M B M M M B A M M L
9 A M M M G L L B A C B L L
10 A M M M L M M A M M M L L
11 B B G L L B A C B L L L L
Step:2 123456789 10111213
1 G C G G L B B L A B B B B
2 C G M M M M M A M B M B C
3 G G M M M M M B M B B C L
4 G L M M M M M B M B M M G
5 L B M M M M M B B C M M C
6 B B L A B B B B C L M M B
7 B M M M B M M M L G M M L
8 L M M M B M M M G C M M L
9 A M M M B C L G C B L L L
10 B M M M C M M C M M M L L
11 B B B C L G C B L L L L L
Step:3 123456789 10111213
1 G B A B L B G L L B B B C
2 B A M M M M M L M B M C C
3 A B M M M M M B M B C C G
4 B L M M M M M B M C M M G
5 L B M M M M M B C C M M B
6 B G L L B B B C C G M M L
7 G M M M B M M M G G M M L
8 L M M M B M M M G B M M L
9 L M M M C C G G B L L L L
10 B M M M C M M B M M M L L
11 B B C C G G B L L L L L L
Step:3 123456789 10111213
1 G C G G L B B C L B B C C
2 C G M M M M M L M B M C B
3 G G M M M M M B M C C B A
4 G L M M M M M B M C M M G
5 L B M M M M M C C B M M C
6 B B C L B B C C B A M M L
7 B M M M B M M M A G M M L
8 C M M M C M M M G C M M L
9 L M M M C B A G C L L L L
10 B M M M B M M C M M M L L
11 B C C B A G C L L L L L L
Step:3 123456789 10111213
1 G B A B L B C C L B C C B
2 B A M M M M M L M C M B A
3 A B M M M M M B M C B A C
4 B L M M M M M C M B M M G
5 L B M M M M M C B A M M B
6 B C C L B C C B A C M M A
7 C M M M C M M M C G M M L
8 C M M M C M M M G B M M L
9 L M M M B A C G B A L L L
10 B M M M A M M B M M M L L
11 C C B A C G B A L L L L L
Step:3 123456789 10111213
1 G C G G L L C C L L C B A
2 C G M M M M M L M C M A C
3 G G M M M M M L M B A C B
4 G L M M M M M C M A M M G
5 L L M M M M M B A C M M C
6 L C C L L C B A C B M M G
7 C M M M C M M M B G M M G
8 C M M M B M M M G C M M L
9 L M M M A C B G C G G L L
10 L M M M C M M C M M M L L
11 C B A C B G C G G L L L L
Step:3 123456789 10111213
1 G B A B C L C C A L G A C
2 B A M M M M M A M G M C B
3 A B M M M M M L M A C B L
4 B C M M M M M G M C M M G
5 C L M M M M M A C B M M B
6 L C C A L G A C B L M M A
7 C M M M G M M M L G M M B
8 C M M M A M M M G B M M C
9 A M M M C B L G B A B C L
10 L M M M B M M B M M M L L
11 G A C B L G B A B C L L L
Step:3 123456789 10111213
1

Step:3 123456789 10111213
1 G B A L C L A A C B G B L
2 B A M M M M M C M G M L L
3 A L M M M M M B M B L L L
4 L C M M M M M G M L M M G
5 C L M M M M M B L L M M B
6 L A A C B G B L L L M M A
7 A M M M G M M M L G M M L
8 A M M M B M M M G B M M A
9 C M M M L L L G B A L A A
10 B M M M L M M B M M M A G
11 G B L L L G B A L A A G L
Step:3 123456789 10111213
1 G C G L C L A C B L G C L
2 C G M M M M M B M G M L L
3 G L M M M M M L M C L L L
4 L C M M M M M G M L M M G
5 C L M M M M M C L L M M C
6 L A C B L G C L L L M M G
7 A M M M G M M M L G M M L
8 C M M M C M M M G C M M A
9 B M M M L L L G C G L A B
10 L M M M L M M C M M M B B
11 G C L L L G C G L A B B A
Step:3 123456789 10111213
1 G B A L C L G B L L G B A
2 B A M M M M M L M G M A L
3 A L M M M M M L M B A L L
4 L C M M M M M G M A M M G
5 C L M M M M M B A L M M B
6 L G B L L G B A L L M M A
7 G M M M G M M M L G M M L
8 B M M M B M M M G B M M L
9 L M M M A L L G B A L L B
10 L M M M L M M B M M M B A
11 G B A L L G B A L L B A C
Step:3 123456789 10111213
1 G C G L C G G C L L G C G
2 C G M M M M M L M G M G G
3 G L M M M M M L M C G G L
4 L C M M M M M G M G M M G
5 C G M M M M M C G G M M C
6 G G C L L G C G G L M M G
7 G M M M G M M M L G M M G
8 C M M M C M M M G C M M L
9 L M M M G G L G C G G L G
10 L M M M G M M C M M M G C
11 G C G G L G C G G L G C B
Step:4 123456789 10111213
1 G B A L G A G B A L G B A
2 B A M M M M M A M G M A B
3 A L M M M M M L M B A B A
4 L G M M M M M G M A M M G
5 G A M M M M M B A B M M B
6 A G B A L G B A B A M M A
7 G M M M G M M M A G M M B
8 B M M M B M M M G B M M A
9 A M M M A B A G B A B A G
10 L M M M B M M B M M M G B
11 G B A B A G B A B A G B L
Step:4 123456789 10111213
1 G C G C G C G C G C G C G
2 C G M M M M M G M G M G B
3 G C M M M M M C M C G B C
4 C G M M M M M G M G M M G
5 G C M M M M M C G B M M C
6 C G C G C G C G B C M M G
7 G M M M G M M M C G M M B
8 C M M M C M M M G C M M C
9 G M M M G B C G C G B C G
10 C M M M B M M C M M M G C
11 G C G B C G C G B C G C L
Step:4 123456789 10111213
1 G B G B G B G B G B G B G
2 B G M M M M M G M G M G B
3 G B M M M M M B M B G B G
4 B G M M M M M G M G M M G
5 G B M M M M M B G B M M B
6 B G B G B G B G B G M M G
7 G M M M G M M M G G M M B
8 B M M M B M M M G B M M G
9 G M M M G B G G B G B G G
10 B M M M B M M B M M M G B
11 G B G B G G B G B G G B G
Step:4 123456789 10111213
1 G G G G G G G G G G G G G
2 G G M M M M M G M G M G G
3 G G M M M M M G M G G G G
4 G G M M M M M G M G M M G
5 G G M M M M M G G G M M G
6 G G G G G G G G G G M M G
7 G M M M G M M M G G M M G
8 G M M M G M M M G G M M G
9 G M M M G G G G G G G G G
10 G M M M G M M G M M M G G
11 G G G G G G G G G G G G G
Step:4 123456789 10111213
1 G B A L L B C C A L L L L G C G G L B B C L L C A A G B A L A A G L C C A A G G C G L C L C A A C G C B T T T T T T T T T T T T T

2 B A M M M M M A M L M L L 2 C G M M M M M L M C M A B 2 B A M M M M M C M A M G L 2 C G M M M M M A M G M B L 2 T T M M M M M T M T M T T

3 A L M M M M M L M L L L L 3 G G M M M M M L M A A B B 3 A L M M M M M C M A G L A 3 G L M M M M M C M C B L L 3 T T M M M M M T M T T T T

4 L L M M M M M L M L M M L 4 G L M M M M M C M A M M C 4 L A M M M M M A M G M M A 4 L C M M M M M G M B M M G 4 T T M M M M M T M T M M T

5 L B M M M M M L L L M M L 5 L B M M M M M A A B M M C 5 A A M M M M M A G L M M B 5 C L M M M M M C B L M M C 5 T T M M M M M T T T M M T

6 B C C A L L L L L L M M L 6 B B C L L C A A B B M M A 6 A G L C C A A G L A M M B 6 L C A A C G C B L L M M G 6 T T T T T T T T T T M M T

7 C M M M L M M M L L M M L 7 B M M M C M M M B C M M L 7 G M M M A M M M A A M M A 7 C M M M G M M M L G M M L 7 T M M M T M M M T T M M T

8 C M M M L M M M L L M M L 8 C M M M A M M M C C M M L 8 L M M M A M M M A B M M C 8 A M M M C M M M G C M M C 8 T M M M T M M M T T M M T

9 A M M M L L L L L L L L L 9 L M M M A B B C C A L L L 9 C M M M G L A A B B A C B 9 A M M M B L L G C G L C A 9 T M M M T T T T T T T T T

10 L M M M L M M L M M M L L 10 L M M M B M M C M M M L L 10 C M M M L M M B M M M B L 10 C M M M L M M C M M M A L 10 T M M M T M M T M M M T T

11 L L L L L L L L L L L L L 11 C A A B B C C A L L L L L 11 A A G L A A B B A C B L L 11 G C B L L G C G L C A L L 11 T T T T T T T T T T T T T

Fig. 6. Snapshots of the proposed 6-state fault-tolerant linear-time firing squad syn-
chronization algorithm on rectangular arrays