The diameter and connectivity of networks with random dependent faults
Networks , Volume 56 - Issue 2 p. 103- 115
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 ε 1/ω(n1/2), and does not when p ε 1/O(n 1/2); a network built of tori is designed, with the same faulttolerance properties and additionally having low diameter. We show, however, that for networks of degree bounded above by a constant δ, the fault-free part can not be connected with high probability if p ε 1/O(n1/δ). This is the first analytic paper which investigates the connectivity and diameter of networks where nodes fail in a random dependent way.