Efficient self-embedding of butterfly networks with random faults
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 533-541
- https://doi.org/10.1109/sfcs.1992.267798
Abstract
The author studies the embedding of the butterfly network in a faulty version of itself where each node is independently faulty with some constant probability. He shows that such a self-embedding of the N-node butterfly with O(1) load, O((log logN)/sup 2.6/) dilation, and 0((log log N)/sup 8.2/) congestion is possible with high probability, assuming sufficiently small node-failure probability. This embedding is level-preserving in the sense that each node is mapped to a node in the same level of the butterfly. He also derives a lower bound of log log log N-c on the dilation of a level-preserving embedding with O(log/sup alpha / N) load, for any alpha , 0< alpha 0, and some constant c depending on alpha and p.Keywords
This publication has 7 references indexed in Scilit:
- Asymptotically tight bounds for computing with faulty arrays of processorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Robust bounded-degree networks with small diametersPublished by Association for Computing Machinery (ACM) ,1992
- On the fault tolerance of some popular bounded-degree networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Coding theory, hypercube embeddings, and fault tolerancePublished by Association for Computing Machinery (ACM) ,1991
- Fault tolerance in hypercube-derivative networksPublished by Association for Computing Machinery (ACM) ,1989
- Work-preserving emulations of fixed-connection networksPublished by Association for Computing Machinery (ACM) ,1989
- Fast computation using faulty hypercubesPublished by Association for Computing Machinery (ACM) ,1989