Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff

Abstract

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^{\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^{\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^{\prime }$, the surviving part of $H$ still contains an BFS spanning tree for (the surviving part of) $G$, satisfying $dist(s,v,H\setminus \{e\})\le dist(s,v,G\setminus \{e\})$ for every $v\in V$ and $e\in E\setminus E^{\prime }$. We establish the following tradeoff between $b(n)$ and $r(n)$: For every real $\epsilon \in (0,1]$, if $r(n)=\tilde{\Theta }(n^{1-\epsilon })$, then $b(n)=\tilde{\Theta }(n^{1+\epsilon })$ is necessary and sufficient.

References in corpus (2)

• Fault-Tolerant Spanners: Better and Simpler
• Sparse Fault-Tolerant BFS Trees