DocumentCode
1139487
Title
Reliable computation by networks in the presence of noise
Author
Feder, Tomas
Author_Institution
Dept. of Comput. Sci., Stanford Univ., CA, USA
Volume
35
Issue
3
fYear
1989
fDate
5/1/1989 12:00:00 AM
Firstpage
569
Lastpage
571
Abstract
Lower bounds on the depth of Boolean networks that can compute reliably in the presence of randomly occurring failures are proved. A bound is also given on the reliability that error-tolerant networks can achieve: this bound implies a limit strictly smaller than 1/2 on the failure probability per gate that can be tolerated. The results improve upon recently published bounds of N. Pippenger (ibid., vol.IT-34, p.194-7, 1988) on the depth of error-tolerant formulas and extend the bounds to the case of reliable computation by networks
Keywords
Boolean functions; fault tolerant computing; Boolean networks; depth bound; error-tolerant networks; failure probability per gate; lower bounds; noise; randomly occurring failures; reliability; reliable computation; Boolean functions; Computer networks; Computer science; Input variables; Intelligent networks; Scholarships;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/18.30978
Filename
30978
Link To Document