Memory in Media with Manufacturing Faults (thesis)

Abstract:

As computational systems scale to arbitrarily large sizes, and as they are
expected to function reliably for arbitrary lengths of time, there are
certain realities of the physical world that can not be ignored in the
design and modeling of computational systems. For example, considerations
for the delivery of power and removal of heat seem to limit the system to a
two-dimensional surface. Additionally, it can be argued that all of the
following restrictions are desirable and reasonable: there is a finite
variety of components, no components (or external agents) are immune to
failure, and components can communicate only with a bounded number of other
components over a bounded distance. A very general model, with a reasonable
ability to capture many of these features, is that of a cellular automaton.

We extend the widely studied model of transient faults (which occur
independently at different places and different times) in cellular automata
to consider manufacturing faults (which occur independently at different
places, but affect cells for all time). Although a well known monotone
binary transition rule (known as Toom's Rule) in two dimensions can remember
a bit (that is, the system can be used to preserve a single Boolean value
for all time with probability one) in the presence of transient faults, we
show that no monotone binary transition rule in two dimensions can remember
a bit when both manufacturing faults and transient faults are present. On
the other hand, we give a monotone binary transition rule in three
dimensions that can remember a bit in the presence of both manufacturing
faults and transient faults. (By adding one or two further dimensions, one
can reduce the problem of performing an arbitrary computation reliably to
the problem of remembering a single bit.) We also study cellular automata
that are based on hyperbolic (rather than Euclidean) tessellations
(including infinite regular trees), and we completely classify the cases in
which majority voting among all nearest neighbors can tolerate manufacturing
faults and/or transient faults.