Recent Progress on Fault Tolerant Spanners

by Greg Bodwin

Oded's comments

This talk is a paragon of what a colloquium talk should be. As the abstract indicates, the speaker focused on giving an insightful and educational survey of a research direction, providing a wide and yet nuanced picture.

The research direction is fault tolerant spanners and emulators, where the stretch is measured wrt to the residual graph (when considering all relevant fault patterns). Key parameters include allowed stretch (i.e, $k$), number of faulty components (i.e., $f$), whether these are vertices or edges, and whether the desired output should be a subgraph of the original graph or a subgraph of the all-pairs distance closure (called emulator).

Specifically, wlog, it suffices to consider the case that $k$ is an odd integer; hence, we let $k=2t-1$. In the non-faulty case, a $(2t-1)$-spanner having $O(n^{1+(1/t)})$ edges can be constructed efficiently, and a $(2t-1)$-emulator cannot have less edges. When $f$ faults are allowed, the first two cases (i.e., $k=3$ and $k=5$) manifest fundamentally different behavior:

An interesting aspect in the positive results, which include efficient algorithms, is that they are derived by referring to a notion that arises naturally from the (straightforward but inefficient) greedy algorithm that examines all possible failure patterns (the number of which is exponential in $f$). Hence, inefficient algorithms are used to derive (indirectly) efficient algorithms.

The original abstract

Given a large input graph, a k-spanner is a sparse subgraph that preserves the shortest path distances of the original within an approximation factor of k. When this distance approximation is robust to f failing nodes or edges, the spanner is f-fault tolerant. Fault tolerant spanners and their relatives arise commonly in networking and distributed computing.

There has been a recent flurry of progress on fault tolerant spanners and their relatives, including faster construction algorithms and better tradeoffs between spanner size, error, and level of fault tolerance. We will survey this progress, spanning a sequence of 7 papers over the last 5 years. We will explain the new techniques that have enabled progress, the problems that have been solved, and the problems that remain open.

Back to list of Oded's choices.