3 Routing around faults

 

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.

• 3.1 Worst case faults
• 3.2 Random faults
• 3.3 On-line reconfiguration