Solution for restoring faulty graphs earns best paper award

Prof. Greg Bodwin has devised a solution to an important open question in graph theory that offers promising new options for repairing and constructing resilient networks. His paper, called “Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs,” was recognized with a Best Paper Award at the 2021 ACM Symposium on Principles of Distributed Computing.

In 2002, a group of researchers at Tel Aviv University developed an important proof about unweighted, undirected graphs. Graphs are a type of data structure that holds data in nodes connected to one another with edges – in this case, edges that don’t arrange the nodes in a certain order (undirected) and edges that are all treated equally (unweighted). A common operation done with graphs is determining the shortest paths between different nodes. The 2002 proof showed that there’s an efficient way to determine new shortest paths on one of these graphs when one of its edges is broken (called the restoration lemma).

The lemma states that in these circumstances, there will always be two other shortest paths from point A to point B (say, from point A to a midpoint between A and B, and then from that midpoint to B) that you can simply join together to reconstruct a new shortest path that covers the full distance.

Bodwin and co-author Merav Parter from the Weizmann Institute of Science tackled a standing shortcoming to this technique – namely, just because these two paths can exist doesn’t mean they’ll be quickly identifiable in every situation. The hole lies in graphs with tiebreaker paths – if there are multiple equally short paths from A to B before an edge is broken, then many algorithms will select one and discard the others. After the edge is broken, there’s no guarantee that the selected shortest paths can be used to restore the original shortest path.

Bodwin and Parter resolve this question with a proof that it’s possible to break these ties in a way that doesn’t make restorations impossible. The key is to select “asymmetric” shortest paths in the initial graph – this means that, for paths between points A and B, you don’t choose the exact same path from A to B and from B to A. Their proof demonstrates that this asymmetry is enough to allow restorable tie-breaking in every graph.

This solution has applications spanning the many uses of graphs, including in the design and analysis of resilient networks. Their paper describes how this solution can be used to design fault-tolerant network distance labeling schemes, fault-tolerant distance preservers, and fast distributed algorithms that construct these objects.