Fault tolerance in cellular automata at low fault rates

DOI10.1016/J.JCSS.2013.02.001zbMATH Open1311.68093arXiv1207.5550OpenAlexW4205437703MaRDI QIDQ394335FDOQ394335

Authors: Mark McCann, Nicholas Pippenger 

Publication date: 27 January 2014

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A simple three-dimensional real-time reliable cellular array
• Symmetry in self-correcting cellular automata
• New tools for cellular automata in the hyperbolic plane
• Title not available (Why is that?)
• Title not available (Why is that?)
• Statistical Analysis of Paged and Segmented Computer Systems
• Title not available (Why is that?)
• Fault tolerance in cellular automata at high fault rates

Cited In (12)

• Cellular automata-based systems with fault-tolerance
• Title not available (Why is that?)
• Fault tolerance in cellular automata at high fault rates
• On a class of PCA with size-3 neighborhood and their applications in percolation games
• Defect-tolerance in cellular nanocomputers
• Increasing fault-tolerance in cellular automata-based systems
• Reliable cellular automata with self-organization
• Fault-tolerant schemes for some systolic systems
• Reliable computation with cellular automata
• A multiprocessor working as a fault-tolerant cellular automaton
• Title not available (Why is that?)
• 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)