An asynchronous two-dimensional self-correcting cellular automaton.

摘要

I investigate the problem of reliable computation in a computation system with unreliable components. The components have a small fixed error probability and the computation must be correct with high probability. Cellular automata are used as the model of computation. These automata have mass parallelism and local connection. Synchronous one, two and three dimensional reliable cellular automata have been shown to exist by Gacs. Using asynchronous cellular automata removes the assumption of a fault-free global synchronization clock underlining a synchronous system. I construct an asynchronous two-dimensional reliable cellular automaton in a manner similar to Gacs. This asynchronous reliable automaton is a hierarchy of self-simulating asynchronous cellular automata. The failure probability decreases super-exponentially in the level of simulation. The existence of the Toom rule in the two-dimensional space makes the task of maintaining the hierarchical structure much simpler. The result gives a solution, although not a simple one, to the open problem posted by Berman and Simon in 1988 asking how to simulate a synchronous computation asynchronously with errors permissible in the synchronization clocks.