Computing Replacement Paths in the CONGEST Model

We present several results on the round complexity of Replacement Paths and Second Simple Shortest Path which are basic graph problems that can address fault tolerance in distributed networks. These are well-studied in the sequential setting, and have algorithms [18, 20, 30, 34] that nearly match their fine-grained complexity [3, 33]. But very little is known about either problem in the distributed setting. We present algorithms and lower bounds for these problems in the CONGEST model, with many of our results being close to optimal.