A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches

Andrew V. Goldberg
Bruce M. Maggs
Serge A. Plotkin

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 time. After reconfiguratuion, the multibutterfly can tolerate f worst-case faults and still route any permutation between some set of inputs and outputs in time.

• 1 Introduction
• 2 Butterflies and Multibutterflies
  • 2.1 Dilated butterflies
  • 2.2 Splitter networks
  • 2.3 Randomly-wired splitter networks and multibutterflies
• 3 Routing around faults
  • 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
• 4 Remarks
• References
• About this document ...