Fault tolerance in cellular automata at low fault rates

DOI10.1016/J.JCSS.2013.02.001MaRDI QIDQ394335zbMATH OpenOpenAlexFDO

Authors Mark McCann, Nicholas Pippenger

Publication date 27 January 2014

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.5550

zbMATH Keywords

majority votingcellular automatafault tolerancehyperbolic tessellation

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Cellular automata (computational aspects) (68Q80)

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.

Recommendations

• Fault tolerance in cellular automata at high fault rates
• Reliable cellular automata with self-organization
• Cellular automata-based systems with fault-tolerance
• Fault-tolerant schemes for some systolic systems
• Increasing fault-tolerance in cellular automata-based systems

Cites work

• scientific article; zbMATH DE number 3122767 (Why is no real title available?)
• scientific article; zbMATH DE number 3656179 (Why is no real title available?)
• scientific article; zbMATH DE number 3688721 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 3494310 (Why is no real title available?)
• scientific article; zbMATH DE number 3304072 (Why is no real title available?)
• scientific article; zbMATH DE number 3076934 (Why is no real title available?)
• A simple three-dimensional real-time reliable cellular array
• Fault tolerance in cellular automata at high fault rates
• New tools for cellular automata in the hyperbolic plane
• Statistical Analysis of Paged and Segmented Computer Systems
• Symmetry in self-correcting cellular automata

Cited in

(12)

• Cellular automata-based systems with fault-tolerance
• scientific article; zbMATH DE number 1432321 (Why is no real title available?)
• Fault tolerance in cellular automata at high fault rates
• Defect-tolerance in cellular nanocomputers
• On a class of PCA with size-3 neighborhood and their applications in percolation games
• Increasing fault-tolerance in cellular automata-based systems
• Fault-tolerant schemes for some systolic systems
• Reliable cellular automata with self-organization
• Reliable computation with cellular automata
• A multiprocessor working as a fault-tolerant cellular automaton
• scientific article; zbMATH DE number 4001491 (Why is no real title available?)
• FAULT-TOLERANT NANOCOMPUTERS BASED ON ASYNCHRONOUS CELLULAR AUTOMATA

This page was built for publication: Fault tolerance in cellular automata at low fault rates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394335)