Expanders might be practical: fast algorithms for routing around faults on multibutterflies
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 384-389
- https://doi.org/10.1109/sfcs.1989.63507
Abstract
Simple deterministic O(log N)-step algorithms for routing packets on a multibutterfly are described. The algorithms are shown to be robust against faults, even in the worst case, and to be efficient from a practical point of view. As a consequence, the multibutterfly is shown to be an excellent candidate for a high-bandwidth, low-diameter switching network underlying a distributed-memory machine.Keywords
This publication has 6 references indexed in Scilit:
- An O (log N ) deterministic packet-routing schemeJournal of the ACM, 1992
- Efficient dispersal of information for security, load balancing, and fault toleranceJournal of the ACM, 1989
- Fast computation using faulty hypercubesPublished by Association for Computing Machinery (ACM) ,1989
- Increasing the size of a network by a constant factor can increase performance by more than a constant factorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Fat-trees: Universal networks for hardware-efficient supercomputingIEEE Transactions on Computers, 1985
- Tight Bounds on the Complexity of Parallel SortingIEEE Transactions on Computers, 1985