License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.21
URN: urn:nbn:de:0030-drops-130992
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13099/
Go to the corresponding LIPIcs Volume Portal

Parter, Merav

Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers

pdf-format:
LIPIcs-DISC-2020-21.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{parter:LIPIcs:2020:13099,
  author =	{Merav Parter},
  title =	{{Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13099},
  URN =		{urn:nbn:de:0030-drops-130992},
  doi =		{10.4230/LIPIcs.DISC.2020.21},
  annote =	{Keywords: Fault Tolerance, Distance Preservers, CONGEST}
}

Keywords: Fault Tolerance, Distance Preservers, CONGEST
Collection: 34th International Symposium on Distributed Computing (DISC 2020)
Issue Date: 2020
Date of publication: 07.10.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI