next up previous
Next: 3.1 The fault model Up: A Parallel Algorithm for Previous: 2.3 Randomly-wired splitter networks

3 Routing around faults


In this section, we present an tex2html_wrap_inline815 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.

Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996