3 Routing around faults

 

In this section, we present an time on-line algorithm for reconfiguring a multibuttery network in the presence of faults. We begin in Section 3.1 by describing the fault model. In Section 3.2 we review the off-line algorithm of Leighton and Maggs. Next, in Section 3.3, we describe the on-line algorithm. To simplify the presentation of the algorithm, we augment the multibutterfly with some additional edges. These edges increase the size and VLSI layout area of the network by at most a constant factor. As it turns out, this additional hardware is not really necessary. We conclude in Section 3.4 by explaining how to implement the algorithm without using these extra edges.

• 3.1 The fault model
• 3.2 The Leighton-Maggs algorithm
• 3.3 On-line reconfiguration
  • 3.3.1 Blocks with too many faults fall asleep
  • 3.3.2 Input blocks count awake switches in output blocks
  • 3.3.3 Output blocks that are not to be erased are marked
  • 3.3.4 Input switches are told whether output blocks are erased
  • 3.3.5 A final look at the constants
• 3.4 Removing the additional edges