A PARALLEL ALGORITHM FOR RECONFIGURING A MULTIBUTTERFLY NETWORK WITH FAULTY SWITCHES

Authors
GOLDBERG AV MAGGS BM PLOTKIN SA
Citation
Av. Goldberg et al., A PARALLEL ALGORITHM FOR RECONFIGURING A MULTIBUTTERFLY NETWORK WITH FAULTY SWITCHES, I.E.E.E. transactions on computers, 43(3), 1994, pp. 321-326
Citations number
12
Categorie Soggetti
Computer Sciences","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
Journal title
I.E.E.E. transactions on computers → ACNP
ISSN journal
00189340
Volume
43
Issue
3
Year of publication
1994
Pages
321 - 326
Database
ISI
SICI code
0018-9340(1994)43:3<321:APAFRA>2.0.ZU;2-K
Abstract
This paper describes a deterministic algorithm for reconfiguring a mul tibutterfly network with faulty switches. Unlike previous reconfigurat ion algorithms, the algorithm is performed entirely by the network, wi thout the aid of any off-line computation, even though many of the swi tches may be faulty. The algorithm reconfigures an N-input multibutter fly network in O(log N) time. After reconfiguration, the multibutterfl y can tolerate f worst-case faults and still route any permutation bet ween some set of N - O(f) inputs and N - O(f) outputs in O(logN) time.