The Leighton-Maggs algorithm consists of two parts. The first part, called erasure, removes some of the outputs from the network. The second part, called fault propagation, removes some of the inputs. The goal of the reconfiguration algorithm is to leave intact a large working subnetwork in which every input can reach every output, and in which the splitters have -expansion, where may be less than , but must be greater than one. The proof that a fault-free multibutterfly can route permutations in time holds for any expansion greater than one [6, 12]. By a similar argument, if , the subnetwork also can route any permutations between its inputs and outputs in time .
The erasure part of the algorithm consists of removing those splitters that contain too many faults. This step requires some off-line computation. Each splitter in the multibutterfly is examined, and if more than an fraction of its input switches are faulty, where and , then the splitter is ``erased'' from the network as are all of the switches that can be reached from the splitter, including outputs on level . In the next section, we will present an on-line algorithm for counting the number of faults in each splitter.
The second part of the algorithm, fault-propagation, is executed by the switches themselves. Working from level backwards, each switch checks 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 it declares itself to be faulty (but does not erase itself). Such a fault is called a propagated fault.
Finally, all of the remaining faulty switches are erased. Since every remaining input in every splitter is linked to at least working upper outputs (if the descendant multibutterfly outputs have not been erased) and working lower outputs (if the corresponding multibutterfly outputs have not been erased), the network has -expansion.
The following pair of lemmas bounds the number of removed inputs and outputs in the case of worst-case faults and random faults, respectively.