The Diameter and Connectivity of Networks with Random Dependent Faults

We study the connectivity and diameter of the fault-free part of n-node networks where nodes fail in a random dependent way. To capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, causing faults in the given node and its neighbors; faults at distance at most 2 become dependent. We investigate the impact of the spot probability on the connectivity and diameter of the fault-free part of the network. We show a network which has a low diameter with high probability, if p <= 1/c log n. We also show that, for constant spot probabilities, most classes of networks do not have their fault-free part connected with high probability. For smaller spot probabilities, connectivity with high probability is supported even by bounded degree networks: the torus supports connectivity with high probability when p is an element of 1/omega (n(1/2)), and does not when p is an element of 1/0(n(1/2)); a network built of tori is designed, with the same fault-tolerance properties and additionally having low diameter. We show, however, that for networks of degree bounded above by a constant A, the fault-free part can not be connected with high probability if p is an element of 1/0(n(1/Delta)). This is the first analytic paper which investigates the connectivity and diameter of networks where nodes fail in a random dependent way. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 56(2)9103-115 2010