Efficient Self-embedding Of Butterfly Networks With Random Faults

Abstract

We study the embedding of the butterfly network in its faulty version, where each node is independently faulty with some constant probability p. We give a method of such self-embedding of the N-node butterfly with O(1) load, O((log log N)2.6) dilation, and O((log log N)c) congestion, which succeeds with probability at least 1 - N-1 if p < 1 - √2/3 ≃ 0.1835, where c is a constant that depends on p; c is about 8.84 for p = 0.1 and approaches log2 40 ≃ 5.32 as p → 0. The method is constructive and in fact yields an N logO(1) N time deterministic algorithm to construct the claimed embedding with the claimed success probability when given the random faulty butterfly. We also show that we can make the dilation as low as O(loglog N), although at the cost of logO(1) N congestion. These embeddings are level-preserving in the sense that each node is mapped to a node in the same level of the butterfly as the original node. We also derive a lower bound of log log N - o(log log N) on the dilation of a level-preserving embedding with Nα load, for any constant α< 1/3 and any constant node-failure probability p > 0. Thus, the bounds on dilation are tight up to a constant factor, as far as level-preserving embeddings are concerned.