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.