In this section, we prove that the multibutterfly is a highly
fault-tolerant network. We start by considering worst case faults in
Section 3.1 and then consider the less
malevolent case of random faults in Section 3.2.
For simplicity, we will assume that , although similar
results can be proved for smaller *d*. On-line algorithms for
reconfiguring around faults are discussed in
Section 3.3.

Mon Jul 22 18:45:42 EDT 1996