Efficient self-embedding of butterfly networks with random faults
Hisao Tamaki · 1992
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 , 00, and some constant c depending on alpha and p.>