The algorithm of Section 3.3 augments
the multibutterfly network with two types of edges. First edges
are added from each switch to switches in the same block. Then
edges are added from each switch to both the upper and lower
blocks at the next level. The second type of edges are easily
removed. Their tasks can be performed by the *d* routing edges
leading from each switch to the upper and lower blocks at the next level.

Removing the first type of edges is more problematic. The basic idea
is to simulate them using the *d* routing edges. We begin by
observing that a randomly-wired splitter is likely to have expansion
both from the inputs to the outputs and from the outputs to the inputs
[7, 12]. Let be the
expansion property from the output blocks (taken together) to their
input block. Then , and will be close
to *2d-1*, provided that is sufficiently small. A set of
input switches in a block of size *M* has at least
output neighbors (counting those in both the upper and
lower blocks). These outputs in turn have at least input neighbors, provided . Thus, as
long as none of the output neighbors are faulty, they can be used to
simulate expansion within the block. This expansion can be used in place
of in the algorithm of
Section 3.3. What if some of these
output neighbors are faulty? This problem can be solved by declaring a
switch to be faulty if *any* of its output neighbors are faulty
(*without propagating any faults*) before the reconfiguration
process begins. This trick may multiply the number of faults in the
network by a factor of *2d*, but if a switch survives then all of its
output neighbors were initially working.

Mon Jul 22 19:56:03 EDT 1996