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.4 Removing the additional edges

Mon Jul 22 19:56:03 EDT 1996