2026-07-23T16:05:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13099 2024-03-06T10:51:33Z ddc:004 open_access

Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers Parter, Merav Fault Tolerance Distance Preservers CONGEST Fault tolerant distance preservers (spanners) are sparse subgraphs that preserve (approximate) distances between given pairs of vertices under edge or vertex failures. So-far, these structures have been studied thoroughly mainly from a centralized viewpoint. Despite the fact fault tolerant preservers are mainly motivated by the error-prone nature of distributed networks, not much is known on the distributed computational aspects of these structures. In this paper, we present distributed algorithms for constructing fault tolerant distance preservers and +2 additive spanners that are resilient to at most two edge faults. Prior to our work, the only non-trivial constructions known were for the single fault and single source setting by [Ghaffari and Parter SPAA'16]. Our key technical contribution is a distributed algorithm for computing distance preservers w.r.t. a subset S of source vertices, resilient to two edge faults. The output structure contains a BFS tree BFS(s,G ⧵ {e₁,e₂}) for every s ∈ S and every e₁,e₂ ∈ G. The distributed construction of this structure is based on a delicate balance between the edge congestion (formed by running multiple BFS trees simultaneously) and the sparsity of the output subgraph. No sublinear-round algorithms for constructing these structures have been known before. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Merav Parter 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.21 urn:nbn:de:0030-drops-130992 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.21 eng https://creativecommons.org/licenses/by/3.0/legalcode