Document Open Access Logo

Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free

Authors Greg Bodwin, Michael Dinitz, Yasamin Nazari

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.20.pdf
  • Filesize: 0.74 MB
  • 22 pages

Document Identifiers

Author Details

Greg Bodwin
  • University of Michigan, Ann Arbor, MI, USA
Michael Dinitz
  • Johns Hopkins University, Baltimore, MD, USA
Yasamin Nazari
  • Universität Salzburg, Austria

Funding

  • Bodwin, Greg: Supported in part by NSF award CCF-2153680.
  • Dinitz, Michael: Supported in part by NSF award CCF-1909111.
  • Nazari, Yasamin: Supported in part by Austrian Science Fund (FWF) grant P 32863-N.

Cite As Get BibTex

Greg Bodwin, Michael Dinitz, and Yasamin Nazari. Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.20

Abstract

A t-emulator of a graph G is a graph H that approximates its pairwise shortest path distances up to multiplicative t error. We study fault tolerant t-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior.
In particular, our main result is that, for (2k-1)-emulators with k odd, we can tolerate a polynomial number of edge faults for free. For example: for any n-node input graph, we construct a 5-emulator (k = 3) on O(n^{4/3}) edges that is robust to f = O(n^{2/9}) edge faults. It is well known that Ω(n^{4/3}) edges are necessary even if the 5-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd k, and whether a similar phenomenon can be proved for even k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • Emulators
  • Fault Tolerance
  • Girth Conjecture

Metrics

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

Related Versions

References

  1. Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence. Graph spanners: A tutorial review. Computer Science Review, 37:100253, 2020. Google Scholar
  2. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81-100, 1993. Google Scholar
  3. Greg Bodwin, Michael Dinitz, and Yasamin Nazari. Epic fail: Emulators can tolerate polynomially many edge faults for free. CoRR, abs/2209.03675, 2022. URL: https://doi.org/10.48550/arXiv.2209.03675.
  4. Greg Bodwin, Michael Dinitz, and Yasamin Nazari. Vertex Fault-Tolerant Emulators. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1-25:22, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.25.
  5. Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. Optimal vertex fault tolerant spanners (for fixed stretch). In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1884-1900. SIAM, 2018. Google Scholar
  6. Greg Bodwin, Michael Dinitz, and Caleb Robelle. Optimal vertex fault-tolerant spanners in polynomial time. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 2021. Google Scholar
  7. Greg Bodwin, Michael Dinitz, and Caleb Robelle. Partially optimal edge fault-tolerant spanners. In Proceedings of the Thirty-Thurd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, 2022. Google Scholar
  8. Greg Bodwin and Shyamal Patel. A trivial yet optimal solution to vertex fault tolerant spanners. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, pages 541-543, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331588.
  9. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault tolerant spanners for general graphs. SIAM J. Comput., 39(7):3403-3423, 2010. Google Scholar
  10. Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages 169-178, 2011. Google Scholar
  11. Michael Dinitz and Caleb Robelle. Efficient and simple algorithms for fault-tolerant spanners. In Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing, PODC ’20, 2020. Google Scholar
  12. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000. Google Scholar
  13. Paul Erdős. Extremal problems in graph theory. In In Theory of Graphs and its Applications, Proc. Sympos. Smolenice, 1964. Google Scholar
  14. Merav Parter. Nearly optimal vertex fault-tolerant spanners in optimal time: Sequential, distributed, and parallel. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 1080-1092, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3520047.
  15. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  16. David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM J. Comput., 18(4):740-747, 1989. 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