Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff

This paper initiates the study of fault resilient network structures that mix two orthogonal protection mechanisms: (a) {\em backup}, namely, augmenting the structure with many (redundant) low-cost but fault-prone components, and (b) {\em 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)$ {\em 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^{\mathrm{\prime }}\subseteq E$ of $r(n)$ fault-resistant {\em reinforcement} edges, which are assumed to never fail, and a (larger) set $E(H)\setminus E^{\mathrm{\prime }}$ of $b(n)$ fault-prone {\em backup} edges, such that subsequent to the failure of a single fault-prone backup edge $e \in E \setminus E’$,thesurvivingpartof$H$ still contains an BFS spanning tree for (the surviving part of) $G$, satisfying $dist(s,v,H\setminus {e}) \leq dist(s,v,G\setminus {e})$forevery$v \in V$and$e \in E \setminus E’$. We establish the following tradeoff between $b(n)$ and $r(n)$: For every real $ϵ\in (0,1]$, if $r(n)=\tilde{\mathrm{\Theta }}(n^{1-ϵ})$, then $b(n) = {\tilde\Theta}(n^{1+\epsilon})$ is necessary and sufficient.