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.
