About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.