Author: Peter Gacs
Title: Reliable Cellular Automata with Self-Organization
Date: Jan. 15, 1998
Abstract:
In a probabilistic cellular automaton in which all local transitions
have positive probability, the problem of keeping a bit of information
for more than a constant number of steps is nontrivial, even in an
infinite automaton.
Still, there is a solution in 2 dimensions, and this solution can be
used to construct a simple 3-dimensional discrete-time universal
fault-tolerant cellular automaton.
This technique does not help much to solve the following problems:
remembering a bit of information in 1 dimension; computing in
dimensions lower than 3; computing in any dimension with
non-synchronized transitions.
Our more complex technique organizes the cells in blocks that
perform a reliable simulation of a second (generalized) cellular
automaton.
The cells of the latter automaton are also organized in blocks,
simulating even more reliably a third automaton, etc.
Since all this (a possibly infinite hierarchy) is organized in
``software'', it must be under repair all the time from damage caused
by errors.
A large part of the problem is essentially self-stabilization
recovering from a mess of arbitrary-size and content caused by the
faults.
The present paper constructs an asynchronous one-dimensional
fault-tolerant cellular automaton, with the further feature of
``self-organization''.
The latter means that unless a large amount of input information must be
given, the initial configuration can be chosen to be periodical with a
small period.