English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 depends)needed 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 $O((1/\xi^2)\log(1/\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$\Omega(1/\xi^2)$, even with purely probabilistic transient faults only.

Fault Tolerance in Cellular Automata at High Fault Rates