Can large fanin circuits perform reliable computations in the presence of faults?

AbstractFor ordinary circuits with a fixed upper bound on the fanin of its gates it has been shown that logarithmic redundancy is necessary and sufficient to overcome random hardware faults (noise). Here, we consider the same question for unbounded fanin circuits which in the fault-free case can compute Boolean functions in sublogarithmic depth. Now the details of the fault model become more important. One may assume that only gates, resp. only wires may deliver wrong values, or that both gates and wires may behave faulty. The fault tolerance depends on the types of gates that are used, and whether the error probabilities are known exactly or only an upper bound for them. Concerning the first distinction the two most important models are circuits consisting of and- and or-gates with arbitrarily many inputs, and circuits built from the more general type of threshold gates. We will show that in case of faulty and/or-circuits as well as threshold circuits an increase of fanin and size cannot be traded for a depth reduction if the error probabilities are unknown. Gates with large fanin are of no use if errors may occur. Circuits of arbitrary size, but fixed depth can compute only a tiny subset of all Boolean functions reliably. Only in case of threshold circuits and exactly known error probabilities redundancy is able to compensate faults. We describe a transformation from fault-free to fault-tolerant circuits that is optimal with respect to depth keeping the circuit size polynomial