| Title | : | Distributed Fault Tolerant Distance Computation in Graphs |
|
|
| Speaker | : |
Vignesh Manoharan (UT Austin) |
|
| Details | : | Fri, Dec 19, 2025 3:00 PM, @ SSB 334 |
| |
|
| Abstract | : | Routing messages is an important problem in distributed networks, and efficient fault-tolerant routing requires methods to maintain shortest distances between nodes when faults occur. In this talk, I will introduce fault-tolerant versions of shortest path problems in graphs, and discuss algorithms and lower bounds for these problems in the "CONGEST" model of bandwidth-limited distributed computation. Specifically, I will present results for the Replacement Paths problem and the Distance Sensitivity Oracle problem which both deal with computing shortest paths in a graph when a single edge fails. |
