next up previous
Next: 1 Introduction

A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches

Andrew V. Goldberg tex2html_wrap_inline533
Bruce M. Maggs tex2html_wrap_inline535
Serge A. Plotkin tex2html_wrap_inline537

Abstract- This paper describes a deterministic algorithm for reconfiguring a multibutterfly network with faulty switches. Unlike previous reconfiguration algorithms, the algorithm is performed entirely by the network, without the aid of any off-line computation, even though many of the switches may be faulty. The algorithm reconfigures an N-input multibutterfly network in tex2html_wrap_inline541 time. After reconfiguratuion, the multibutterfly can tolerate f worst-case faults and still route any permutation between some set of tex2html_wrap_inline545 inputs and tex2html_wrap_inline547 outputs in tex2html_wrap_inline549 time.

Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996
anonymous logging image