An asynchronous two-dimensional self-correcting cellular automaton

Abstract

Earlier work of P. Gacs and J. Reif (J. Comput. Syst. Sci., vol. 36, no. 2, pp. 125-147, 1988) on reliable computation using cellular automata is extended to asynchronous cellular automata. The goal is to find ways to implement computations of arbitrary size by a homogeneous asynchronous array of unreliable elementary components. An asynchronous two-dimensional cellular automaton is constructed so that given any computation and reliability requirement, a program can be found for such an automaton that performs the computation with probability that meets the reliability requirement. This is the strongest among the published results on reliable computation in an asynchronous environment. It is stronger than its asynchronous counterpart in the sense that it removes the assumption of a fault-free global synchronization clock underlying a synchronous system.