Abstract | ||
---|---|---|
This paper initiates the study of fault resilient network structures that mix two orthogonal protection mechanisms:(a) backup, namely, augmenting the structure with many (redundant) low-cost but fault-prone components, and (b) reinforcement, namely, acquiring high-cost but fault-resistant components. To study the trade-off between these two mechanisms in a concrete setting, we address the problem of designing a (b,r) fault-tolerant BFS (or (b,r) FT-BFS for short) structure,namely, a subgraph H of the network G consisting of two types of edges: a set E' ⊆ E of r(n) fault-resistant reinforcement edges, which are assumed to never fail, and a (larger) set E(H) \\ E' of b(n) fault-prone backup edges, such that subsequent to the failure of a single fault-prone backup edge e ∈ E \\ E', the surviving part of H still contains a BFS spanning tree for (the surviving part of) G, satisfying dist(s,v,H\\{e}) ≤ dist(s,v,G \\{e}) for every v ∈ V and e ∈ E \\ E'.We establish the following tradeoff: For every real ε ∈ (0,1], if r(n) = Θ(n1-ε),then b(n) = Θ(n{1+ε) is necessary and sufficient.More specifically, as shown in ESA'13, for ε=1, FT-BFS structures (with no reinforced edges) require Θ(n3/2) edges, and this is sufficient. At the other extreme, if ε=0, then n-1 reinforced edges suffice (with no need for backup). Here, we present a polynomial time algorithm that given an undirected graph G=(V,E), a source vertex s and a real ε ∈ (0,1], constructs a (b(n),r(n)) FT-BFS with r(n) = O(n1-ε) and b(n) = O(min{1/ε • n1+ε • log n, n3/2). We complement this result by providing a nearly matching lower bound, showing that there are n-vertex graphs for which any (b(n),r(n)) FT-BFS structure requires Ω(min{n{1+ε, n3/2}) backup edges when r(n)=Ω(n1-ε) edges are reinforced. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1145/2755573.2755590 | ACM Symposium on Parallelism in Algorithms and Architectures |
Keywords | Field | DocType |
Fault-tolerance,replacement-paths,tree-decomposition | Discrete mathematics,Binary logarithm,Combinatorics,Vertex (geometry),Upper and lower bounds,Tree decomposition,Fault tolerance,Spanning tree,Time complexity,Mathematics,Backup | Journal |
Volume | Citations | PageRank |
abs/1504.04169 | 0 | 0.34 |
References | Authors | |
20 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Merav Parter | 1 | 169 | 32.59 |
David Peleg | 2 | 6662 | 824.19 |