Reliable Computation by Formulas in the Presence of Noise

Abstract

It is shown that if formulas are used to compute Boolean functions in the presence of randomly occurring failures (as has been suggested by von Neumann and others), then 1) there is a limit strictly less than 1/2 to the failure probability per gate that can be tolerated, and 2) formulas that tolerate failures must be deeper (and, therefore, compute more slowly) than those that do not. © 1988 IEEE