Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs

DOI10.1145/3465084.3467913arXiv2102.10174OpenAlexW3184184852MaRDI QIDQ6201972FDOQ6201972

Authors: Greg Bodwin, M. Parter 

Publication date: 26 March 2024

Published in: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [Dist. Comp. '02] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is tiebreaking-sensitive: if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two selected shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible. We settle this question affirmatively with the first general construction of restorable tiebreaking schemes. We then show applications to various problems in fault-tolerant network design. These include a faster algorithm for subset replacement paths, more efficient fault-tolerant (exact) distance labeling schemes, fault-tolerant subset distance preservers and $+4$ additive spanners with improved sparsity, and fast distributed algorithms that construct these objects. For example, an almost immediate corollary of our restorable tiebreaking scheme is the first nontrivial distributed construction of sparse fault-tolerant distance preservers resilient to three faults.

Full work available at URL: https://arxiv.org/abs/2102.10174

Recommendations

• Efficient oracles and routing schemes for replacement paths
• scientific article; zbMATH DE number 6850433
• Preserving distances in very faulty graphs
• Approximate Single-Source Fault Tolerant Shortest Path

zbMATH Keywords

distributed algorithmsfault tolerancespannerslabeling schemesreplacement pathsshortest path tiebreaking

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

This page was built for publication: Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201972)