4.3. 4.3 Expensive fault-tolerance in Boolean circuits

Let be a Boolean circuit as given in Definition 4.7. When noise is allowed then the values

will not be determined by the formula (4.11) anymore. Instead, they will be random variables . The random assignment will be called a random configuration.

Definition 4.11 At vertex , let

Figure 4.4.  Failure at a gate.

Failure at a gate.


In other words, if gate is not equal to the value computed by the noise-free gate from its inputs . (See Figure 4.4.) The set of vertices where is non-zero is the set of faults.

Let us call the difference the deviation at node .

Let us impose conditions on the kind of noise that will be allowed. Each fault should occur only with probability at most , two specific faults should only occur with probability at most , and so on.

Definition 4.12 For an , let us say that the random configuration is -admissible if

(a) for .

(b) For every set of non-input nodes, we have

In other words, in an -admissible random configuration, the probability of having faults at different specific gates is at most . This is how we require that not only is the fault probability low but also, faults do not “conspire”. The admissibility condition is satisfied if faults occur independently with probability .

Our goal is to build a circuit that will work correctly, with high probability, despite the ever-present noise: in other words, in which errors do not accumulate. This concept is formalized below.

Definition 4.13 We say that the circuit with output node is -resilient if for all inputs , all -admissible configurations , we have .

Let us explore this concept. There is no -resilient circuit with , since even the last gate can fail with probability . So, let us, a little more generously, allow . Clearly, for each circuit and for each we can choose small enough so that is -resilient. But this is not what we are after: hopefully, one does not need more reliable gates every time one builds a larger circuit. So, we hope to find a function

and an with the property that for all , , every Boolean circuit of size there is some -resilient circuit of size computing the same function as . If we achieve this then we can say that we prevented the accumulation of errors. Of course, we want to make relatively small, and large (allowing more noise). The function can be called the redundancy: the factor by which we need to increase the size of the circuit to make it resilient. Note that the problem is nontrivial even with, say, . Unless the accumulation of errors is prevented we will lose gradually all information about the desired output, and no could be guaranteed.

How can we correct errors? A simple idea is this: do “everything” 3 times and then continue with the result obtained by majority vote.

Definition 4.14 For odd natural number , a -input majority gate is a Boolean function that outputs the value equal to the majority of its inputs.

Note that a -input majority can be computed using gates of type AND and NOT.

Why should majority voting help? The following informal discussion helps understanding the benefits and pitfalls. Suppose for a moment that the output is a single bit. If the probability of each of the three independently computed results failing is then the probability that at least of them fails is bounded by . Since the majority vote itself can fail with some probability the total probability of failure is bounded by . We decrease the probability of failure, provided the condition holds.

We found that if is small, then repetition and majority vote can “make it” smaller. Of course, in order to keep the error probability from accumulating, we would have to perform this majority operation repeatedly. Suppose, for example, that our computation has stages. Our bound on the probability of faulty output after stage is . We plan to perform the majority operation after each stage . Let us perform stage three times. The probability of failure is now bounded by

Here, the error probabilities of the different stages accumulate, and even if we only get a bound . So, this strategy will not work for arbitrarily large computations.

Here is a somewhat mad idea to avoid accumulation: repeat everything before the end of stage three times, not only stage itself. In this case, the growing bound (4.15) would be replaced with

Now if and then also , so errors do not accumulate. But we paid an enormous price: the fault-tolerant version of the computation reaching stage is 3 times larger than the one reaching stage . To make stages fault-tolerant this way will cost a factor of in size. This way, the function introduced above may become exponential in .

The theorem below formalizes the above discussion.

Theorem 4.15 Let be a finite and complete basis for Boolean functions. If then every function can be computed by an -resilient circuit over .

Proof. For simplicity, we will prove the result for a complete basis that contains the three-argument majority function and contains not functions with more than three arguments. We also assume that faults occur independently. Let be a noise-free circuit of depth computing function . We will prove that there is an -resilient circuit of depth computing . The proof is by induction on . The sufficient conditions on and will emerge from the proof.

The statement is certainly true for , so suppose . Let be the output gate of the circuit , then . The subcircuits computing the functions have depth . By the inductive assumption, there exist -resilient circuits of depth that compute . Let be a new circuit containing copies of the circuits (with the corresponding input nodes merged), with a new node in which is computed as is applied to the outputs of . Then the probability of error of is at most if since each circuit can err with probability and the node with gate can fail with probability .

Let us now form by taking three copies of (with the inputs merged) and adding a new node computing the majority of the outputs of these three copies. The error probability of is at most . Indeed, error will be due to either a fault at the majority gate or an error in at least two of the three independent copies of . So under condition

the circuit is -resilient. This condition will be satisfied by .

The circuit constructed in the proof above is at least times larger than . So, the redundancy is enormous. Fortunately, we will see a much more economical solution. But there are interesting circuits with small depth, for which the factor is not extravagant.

Theorem 4.16 Over the complete basis consisting of all 3-argument Boolean functions, for all sufficiently small , if then for each there is an -resilient Boolean circuit of input size , depth and size outputting a near-majority (as given in Definition 4.9).

Proof. Apply Theorem 4.15 to the circuit from part (a) of Theorem 4.10: it gives a new, -deep -resilient circuit computing a near-majority. The size of any such circuit with 3-input gates is at most

Exercises

4.3-1 Exercise 4.2-5 suggests that the iterated majority vote is not safe against manipulation. However, it works very well under some circumstances. Let the input to be a vector of independent Boolean random variables with . Denote the (random) output bit of the circuit by . Assuming that our majority gates can fail with probability independently, prove

Hint. Define , , , and prove .

4.3-2 We say that a circuit computes the function in an -input-robust way, if the following holds: For any input vector , for any vector of independent Boolean random variables “perturbing it” in the sense , for the output of circuit on input we have . Show that if the function is computable on an -input-robust circuit then .