Document Open Access Logo

Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers

Author Merav Parter

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.21.pdf
  • Filesize: 0.67 MB
  • 17 pages

Document Identifiers

Author Details

Merav Parter
  • Weizmann Institute of Science, Rehovot, Israel

Funding

Partially funded by the ISF, grant no. 713130.

Cite As Get BibTex

Merav Parter. Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.21

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.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
Keywords
  • Fault Tolerance
  • Distance Preservers
  • CONGEST

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Shiri Chechik, and Sarel Cohen. Deterministic combinatorial replacement paths and distance sensitivity oracles. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 12:1-12:14, 2019. Google Scholar
  2. Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci, and Guido Proietti. Improved purely additive fault-tolerant spanners. In Algorithms-ESA 2015, pages 167-178. Springer, 2015. Google Scholar
  3. Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving distances in very faulty graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  4. Gilad Braunschvig, Shiri Chechik, David Peleg, and Adam Sealfon. Fault tolerant additive and (μ, α)-spanners. Theor. Comput. Sci., 580:94-100, 2015. Google Scholar
  5. Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff. Distributed construction of purely additive spanners. Distributed Computing, 31(3):223-240, 2018. Google Scholar
  6. Shiri Chechik and Sarel Cohen. Near optimal algorithms for the single source replacement paths problem. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2090-2109, 2019. Google Scholar
  7. Shiri Chechik and Ofer Magen. Near optimal algorithm for the directed single source replacement paths problem. CoRR, abs/2004.13673, 2020. Google Scholar
  8. Michael Elkin and Shaked Matar. Near-additive spanners in low polynomial deterministic CONGEST time. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 531-540, 2019. Google Scholar
  9. Yuval Emek, David Peleg, and Liam Roditty. A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Transactions on Algorithms (TALG), 6(4):1-13, 2010. Google Scholar
  10. Mohsen Ghaffari. Near-optimal scheduling of distributed algorithms. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC, pages 3-12, 2015. Google Scholar
  11. Mohsen Ghaffari and Merav Parter. Near-optimal distributed algorithms for fault-tolerant tree structures. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 387-396, 2016. Google Scholar
  12. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 748-757. IEEE, 2012. Google Scholar
  13. Manoj Gupta and Shahbaz Khan. Multiple source dual fault tolerant bfs trees. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  14. Frank Thomson Leighton, Bruce M Maggs, and Satish B Rao. Packet routing and job-shop scheduling ino (congestion+ dilation) steps. Combinatorica, 14(2):167-186, 1994. Google Scholar
  15. Enrico Nardelli, Guido Proietti, and Peter Widmayer. Finding the most vital node of a shortest path. Theoretical computer science, 296(1):167-177, 2003. Google Scholar
  16. Enrico Nardelli, Ulrike Stege, and Peter Widmayer. Low-cost fault-tolerant spanning graphs for point aets in the euclidean plane, 1997. Google Scholar
  17. Merav Parter. Dual failure resilient bfs structure. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 481-490, 2015. Google Scholar
  18. Merav Parter. Vertex fault tolerant additive spanners. Distributed Computing, 30(5):357-372, 2017. Google Scholar
  19. Merav Parter and David Peleg. Sparse fault-tolerant BFS structures. ACM Trans. Algorithms, 13(1):11:1-11:24, 2016. Google Scholar
  20. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  21. Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 253-262, 2008. Google Scholar
  22. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Transactions on Algorithms (TALG), 8(4):1-11, 2012. Google Scholar
  23. Jeanette P Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223-250, 1995. Google Scholar
  24. Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Transactions on Algorithms (TALG), 9(2):1-13, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact