Oded's choices (Nr. 341)

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:

For stretch $k=3$ (i.e., $t=2$), emulators are not better than spanners, and there is no difference between vertex and edge failures. Specifically, in all cases the ``cost'' of fault-tolerance is a factor of $sqrt(f)$ in the number of required edges.
For stretch $k=5$ (i.e., $t=3$), emulators are better than spanners, and there is a difference between vertex and edge failures. Specifically, emulators for edge-failures come for free (i.e., the number of required edges is essentially as in the non-faulty case), whereas this is not the case in the other three combinations. In fact, all results extend to any odd $t$ (equiv $k$ congruent to 1 mod 4); that is, for stretch $k=2t-1$ (s.t. $t$ is odd),
1. For spanners, edge-fault-tolerant comes at a cost of a factor of $f^{0.5+(1/2t)}$ in the number of required edges.
2. For spanners, vertex-fault-tolerant comes at a cost of a factor of $f^{1-(1/t)}$ in the number of required edges.
3. For emulators, vertex-fault-tolerant comes at a cost of a factor of $f^{0.5+(1/2t)}$ in the number of required edges.
The case of even $t\geq4$ is still open.

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.