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.
Publication
STOC 1994
Conference paper
On the fault tolerance of the butterfly
Abstract
We study the robustness of the butterfly network against random static faults. Suppose that each edge of the butterfly is present independently of other edges with probability p. Our main result is that there is a 0-1 law on the existence of a linear- sized component. More formally, there is a critical probability p∗ such that for p above p∗ the faulted butterfly almost surely contains a linear-sized component, whereas for p below p∗, the faulted butterfly almost surely does not contain a linear-sized component.