The Effect of Faults on Network Expansion
Title: The Effect of Faults on Network Expansion
Research Question: How do faults affect the expansion of a network?
Methodology: The researchers used a pruning technique to cull away parts of the faulty network that have poor expansion. This technique can be applied to both adversarial faults and random faults. For adversarial faults, they proved that for every network with expansion α, a large connected component with basically the same expansion as the original fault-free network exists for up to a constant times α·nfaults. This result is tight in the sense that every graph of size n and uniform expansion α(·), i.e., the graph has an expansion of α(n), and every subgraph of size m of the graph has an expansion of O(α(m)), can be broken into sublinear components with ω(α(n)·n) faults.
For random faults, 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. The researchers introduced the span of a graph, which allows them to determine the maximum fault probability in a much better way than the expansion can. They used the span to show the first known results for the effect of random faults on the expansion of a network.
Results: The researchers found that networks of uniform expansion O(√n) can be resilient against a constant fault probability but there are also networks of uniform expansion Ω(1/logn) that are not resilient against a O(1/logn) fault probability.
Implications: These findings have significant implications for the design and analysis of fault-tolerant networks. They provide insights into how many faults a network can sustain while maintaining a large connected component and how the expansion of a network can be used to measure its resilience to faults. The results also highlight the need for a different parameter to better understand the effect of random faults on network expansion.
Link to Article: https://arxiv.org/abs/0404029v1 Authors: arXiv ID: 0404029v1