Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff

Merav Parter, David Peleg

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 {\em 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 an 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 between b(n) andr(n): For every real ϵ∈(0,1], if r(n)=Θ~(n1−ϵ), then b(n)=Θ~(n1+ϵ) is necessary and sufficient.

Guest: Merav Parter
Host: Yvonne-Anne Pignolet