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
[6].

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.

Mon Jul 22 19:56:03 EDT 1996