Error Detection and Correction Algorithms for the Firing Squad Synchronization Problem
Apostolos Kyritsis, Orestis Liolis and Georgios Ch. Sirakoulis
One of the most famous problems in computer science and cellular automata (CAs) is the Firing Squad Synchronization Problem (FSSP). In the FSSP, a one-dimensional CA with just a single active cell (initially called “General“) eventually reaches a state in which all the CA cells (called “soldiers” in analogy to real-world firing squad) are simultaneously active. Since the introduction of the FSSP as a well known problem in the 60’s, and during the last decades, many FSSP solution algorithms have been proposed in the literature. Nevertheless, the inherited error correction capabilities of these algorithms have not been extensively studied. In this paper, an error detection and correction algorithm that utilizes the patterns appearing in 1-D Mazoyer’s 8-state solution is analyzed and presented. Furthermore, the patterns of 2-D Umeo’s FSSP algorithm are also thoroughly investigated. In such a case, extra patterns emerge from CA cells grouping, during the application of 1-D FSSP solution to 2-D CA grid, enhancing the error tolerance of the proposed algorithm, i.e. almost every possible error can be detected. Finally, another version, even more efficient, of error detection and correction algorithm with memory effect considering previous CA states usage, is also introduced. Although the usage of previous CA states results to increased utilization of computational resources, at the same time it enables the proposed algorithm to detect every possible error state in every possible CA cell, advancing significantly the algorithm’s performance.
Keywords: Error detection and correction algorithm, firing squad synchronization problem, 1-D and 2-D cellular automata