Next: 3.2 Random faults Up: 3 Routing around faults Previous: 3 Routing around faults

## 3.1 Worst case faults

In this section, we will prove that no matter how an adversary selects f switches to be faulty, there are always at least inputs and outputs through which any permutation on those inputs and outputs can be routed in steps. In fact, the greedy algorithm described in Section 2 works once we have removed an appropriate set of switches which include at most inputs and outputs.

We first describe which outputs to remove. Examine each splitter in the multibutterfly and check if more than an fraction of the input switches are faulty, where and . If so, then ``erase'' the splitter from the network as well as all descendant switches and outputs. The following lemma bounds the number of erased outputs.

Proof: The erasure of an M-input splitter causes the removal of M multibutterfly outputs, and accounts for at least faults. Hence, at most multibutterfly outputs are removed by this process.

to .667emto .667em

We next describe which inputs to remove. Working from level backwards, examine each switch to see if at least half of its upper output edges lead to faulty switches that have not been erased, or if at least half of its lower output edges lead to faulty switches that have not been erased. If so, then declare the switch to be faulty (but do not erase it). In the following lemmas, we will prove that at most additional switches are declared to be faulty at each level of this process. Hence, at most multibutterfly inputs will be faulty (declared or otherwise).

Proof: The proof is by induction on the level, starting at level and working backwards. The base case at level is trivial since there are no propagated faults on level . Now consider an arbitrary M-input splitter on level i. Let denote the set of faults propagated from the splitter's upper outputs and let denote those propagated from the lower outputs. If the upper outputs were erased, then . Otherwise, the number of faults placed by the adversary in the upper outputs is at most . Since each propagated input fault is connected to at most working upper outputs, we can conclude that . By induction, and . For and , we have a contradiction. A similar argument shows that .

to .667emto .667em

Proof: The proof is again by induction on the level. Consider some level l and assume that it has more than propagated faults. By Lemma 3.2, we know that these faults are divided among the splitters linking level l to l+1 so that we can apply the expansion property to the faults within each splitter. Hence there must be more than faults on level l+1. This is a contradiction however, since level l+1 can have at most total faults by induction. Hence, level l can have at most propagated faults.

to .667emto .667em

We now erase all the remaining faulty switches. This leaves a network with inputs and outputs. Moreover, every input in every splitter is linked to functioning upper outputs (if the descendant multibutterfly outputs exist) and functioning lower outputs (if the corresponding multibutterfly outputs exist). Hence every splitter has an expansion property. Thus, we can apply Theorem 2.1 with replaced by to prove that the greedy algorithm still routes any permutation on the remaining inputs and outputs in steps. This is summarized as Theorem 3.4 below. (Note that we can achieve expansion for .)

Proof: The results follows from Theorem 2.1, Lemmas 3.1 and 3.3, and the fact that .

to .667emto .667em

Next: 3.2 Random faults Up: 3 Routing around faults Previous: 3 Routing around faults

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996