Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/111227
Title: An asynchronous two-dimensional self-correcting cellular automaton
Authors: Wang, Weiguo 
Issue Date: Dec-1991
Citation: Wang, Weiguo (1991-12). An asynchronous two-dimensional self-correcting cellular automaton. Annual Symposium on Foundations of Computer Science (Proceedings) : 278-285. ScholarBank@NUS Repository.
Abstract: Earlier work of P. Gacs and J. Reif (J. Comput. Syst. Sci., vol. 36, no. 2, pp. 125-147, 1988) on reliable computation using cellular automata is extended to asynchronous cellular automata. The goal is to find ways to implement computations of arbitrary size by a homogeneous asynchronous array of unreliable elementary components. An asynchronous two-dimensional cellular automaton is constructed so that given any computation and reliability requirement, a program can be found for such an automaton that performs the computation with probability that meets the reliability requirement. This is the strongest among the published results on reliable computation in an asynchronous environment. It is stronger than its asynchronous counterpart in the sense that it removes the assumption of a fault-free global synchronization clock underlying a synchronous system.
Source Title: Annual Symposium on Foundations of Computer Science (Proceedings)
URI: http://scholarbank.nus.edu.sg/handle/10635/111227
ISBN: 0818624450
ISSN: 02725428
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

76
checked on Oct 23, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.