Premium
The diameter and connectivity of networks with random dependent faults
Author(s) -
Kranakis Evangelos,
Paquette Michel,
Pelc Andrzej
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20352
Subject(s) - bounded function , node (physics) , constant (computer programming) , degree (music) , fault (geology) , fault tolerance , computer science , combinatorics , mathematics , topology (electrical circuits) , discrete mathematics , distributed computing , physics , mathematical analysis , quantum mechanics , seismology , acoustics , programming language , geology
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/ω( n 1/2 ), and does not when p ε 1/ O ( 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 Δ, the fault‐free part can not be connected with high probability if p ε 1/ O ( n 1/Δ ). This is the first analytic paper which investigates the connectivity and diameter of networks where nodes fail in a random dependent way. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010