Merav Parter: "Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff
Friday, September 25, 2015 - 1:00pm to 2:30pm
Location:
32-G631
Speaker:
Merav Parter
Biography:
MIT
Seminar group:
We introduce 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 initiate the study of the tradeoff between reinforcement and backup in survivable network design, we consider the concrete problem of designing (in the mixed model) a fault-tolerant Breadth-First structure (or FT-BFS for short), namely, a subnetwork that preserves distances with respect to a given source vertex in the presence of an edge failure. We will present a nearly optimal tradeoff for BFS structures and discuss some related open problems.