Fault Tolerance in Cellular Automata at High Fault Rates - Mathematics > Probability

Abstract: A commonly used model for fault-tolerant computation is that of cellularautomata. The essential difficulty of fault-tolerant computation is present inthe special case of simply remembering a bit in the presence of faults, andthat is the case we treat in this paper. We are concerned with the degree thenumber of neighboring cells on which the state transition function dependsneeded to achieve fault tolerance when the fault rate is high nearly 1-2. Weconsider both the traditional transient fault model where faults occurindependently in time and space and a recently introduced combined fault modelwhich also includes manufacturing faults which occur independently in space,but which affect cells for all time. We also consider both a purelyprobabilistic fault model in which the states of cells are perturbed atexactly the fault rate and an adversarial model in which the occurrence of afault gives control of the state to an omniscient adversary. We show thatthere are cellular automata that can tolerate a fault rate $1-2 - \xi$ with$\xi>0$ with degree $O1-\xi^2\log1-\xi$, even with adversarial combinedfaults. The simplest such automata are based on infinite regular trees, but ourresults also apply to other structures such as hyperbolic tessellations thatcontain infinite regular trees. We also obtain a lower bound of$\Omega1-\xi^2$, even with purely probabilistic transient faults only.

Author: Mark McCann, Nicholas Pippenger

Source: https://arxiv.org/