Recovery from a Soft Error in Cellular Automata Solving Firing Squad Synchronization Problem
Taishin Y. Nishida
A soft error in cellular automata (CA) is a temporal miss mapping of the local function in a cell. Because the error is temporal, caused by noise, etc, the cell works correctly in the next steps. In this paper we propose a method (or an algorithm) which converts any CA solving firing squad synchronization problem (FSSP) to new CA such that the CA recover one soft error if the error makes an undefined domain of the local function. The method first alters the local function to produce a reset state if the domain is undefined. Then the reset state propagates to left and right making any states to the soldiers. Once the reset state reaches to the left boundary, the state of the general is produced and FSSP restarts. It is proved that the reset and retry actions eventually recovers the soft error and achieves the synchronization.
Keywords: Firing squad synchronization problem, error recovery, soft error, fault tolerant