Fault Tolerance in Cellular Automata at Low Fault Rates
Document Type
Article
Department
Mathematics (HMC)
Publication Date
2013
Abstract
A commonly used model for fault-tolerant computation is that of cellular automata. The essential difficulty of fault-tolerant computation is present in the special case of simply remembering a bit in the presence of faults, and that is the case we treat in this paper. The conceptually simplest mechanism for correcting errors in a cellular automaton is to determine the next state of a cell by taking a majority vote among its neighbors (including the cell itself, if necessary to break ties). We are interested in which regular two-dimensional tessellations can tolerate faults using this mechanism, when the fault rate is sufficiently low. We consider both the traditional transient fault model (where faults occur independently in time and space) and a recently introduced combined fault model which also includes manufacturing faults (which occur independently in space, but which affect cells for all time). We completely classify regular two-dimensional tessellations as to whether they can tolerate combined transient and manufacturing faults, transient faults but not manufacturing faults, or not even transient faults.
Rights Information
© 2013 Elsevier Ltd.
Terms of Use & License Information
DOI
10.1016/j.jcss.2013.02.001
Recommended Citation
Mark McCann, Nicholas Pippenger, Fault tolerance in cellular automata at low fault rates, Journal of Computer and System Sciences, Volume 79, Issue 7, November 2013, Pages 1126-1143, ISSN 0022-0000, 10.1016/j.jcss.2013.02.001. (http://www.sciencedirect.com/science/article/pii/S0022000013000482)
