The effect of faults on network expansion

DOI10.1007/S00224-006-1349-0zbMATH Open1113.68014DBLPjournals/mst/BagchiBCES06arXivcs/0404029OpenAlexW1998076608WikidataQ56428734 ScholiaQ56428734MaRDI QIDQ863198FDOQ863198

Authors: Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, Christian Scheideler 

Publication date: 25 January 2007

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: In this paper we study the problem of how resilient networks are to node faults. Specifically, we investigate the question of how many faults a network can sustain so that it still contains a large (i.e. linear-sized) connected component that still has approximately the same expansion as the original fault-free network. For this we apply a pruning technique which culls away parts of the faulty network which have poor expansion. This technique can be applied to both adversarial faults and to random faults. For adversarial faults we prove that for every network with expansion alpha, a large connected component with basically the same expansion as the original network exists for up to a constant times alpha n faults. This result is tight in the sense that every graph G of size n and uniform expansion alpha(.), i.e. G has an expansion of alpha(n) and every subgraph G' of size m of G has an expansion of O(alpha(m)), can be broken into sublinear components with omega(alpha(n) n) faults. For random faults we observe that the situation is significantly different, because in this case the expansion of a graph only gives a very weak bound on its resilience to random faults. More specifically, there are networks of uniform expansion O(sqrt{n}) that are resilient against a constant fault probability but there are also networks of uniform expansion Omega(1/log n) that are not resilient against a O(1/log n) fault probability. Thus, a different parameter is needed. For this we introduce the span of a graph which allows us to determine the maximum fault probability in a much better way than the expansion can. We use the span to show the first known results for the effect of random faults on the expansion of d-dimensional meshes.

Full work available at URL: https://arxiv.org/abs/cs/0404029

Recommendations

• Random regular graphs with edge faults: Expansion through cores
• scientific article; zbMATH DE number 1361486
• Analysis of edge deletion processes on faulty random regular graphs.
• Construction of the mesh and the torus tolerating a large number of faults
• Expander properties in random regular graphs with edge faults

zbMATH Keywords

node faultsresilient networks

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Network design and communication in computer systems (68M10)

Cited In (5)

• The diameter and connectivity of networks with random dependent faults
• Distributed agreement in dynamic peer-to-peer networks
• Towards robust and efficient computation in dynamic peer-to-peer networks
• Analysis of edge deletion processes on faulty random regular graphs.
• Fault-tolerant graph realizations in the congested clique

This page was built for publication: The effect of faults on network expansion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q863198)