More Web Proxy on the site http://driver.im/

research-article

Fault-tolerant spanners: better and simpler

Authors:

Michael Dinitz,

Robert KrauthgamerAuthors Info & Claims

PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Pages 169 - 178

https://doi.org/10.1145/1993806.1993830

Published: 06 June 2011 Publication History

Abstract

A natural requirement for many distributed structures is fault-tolerance: after some failures in the underlying network, whatever remains from the structure should still be effective for whatever remains from the network. In this paper we examine spanners of general graphs that are tolerant to vertex failures, and significantly improve their dependence on the number of faults r for all stretch bounds.

For stretch k e 3 we design a simple transformation that converts every k-spanner construction with at most f(n) edges into an r-fault-tolerant k-spanner construction with at most O(r³ log n) Å f(2n/r) edges. Applying this to standard greedy spanner constructions gives r-fault tolerant k-spanners with Õ(r² n^1+2/k+1) edges. The previous construction by Chechik, Langberg, Peleg, and Roddity [STOC 2009] depends similarly on n but exponentially on r (approximately like k^r).

For the case of k=2 and unit edge-lengths, an O(r log n)-approximation is known from recent work of Dinitz and Krauthgamer [STOC 2011], in which several spanner results are obtained using a common approach of rounding a natural flow-based linear programming relaxation. Here we use a different (stronger) LP relaxation and improve the approximation ratio to O(log n), which is, notably, independent of the number of faults r. We further strengthen this bound in terms of the maximum degree by using the Lovasz Local Lemma.

Finally, we show that most of our constructions are inherently local by designing equivalent distributed algorithms in the LOCAL model of distributed computation.

References

[1]

I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete Comput. Geom., 9(1):81--100, 1993.

Digital Library

[2]

B. Awerbuch and D. Peleg. Sparse partitions. In 31st Annual IEEE Symposium on Foundations of Computer Science, pages 503--513, 1990.

Digital Library

[3]

B. Awerbuch and D. Peleg. Online tracking of mobile users. J. ACM, 42(5):1021--1058, 1995.

Digital Library

[4]

N. Alon, R. Yuster, and U. Zwick. Color-coding. J. ACM, 42(4):844--856, 1995.

Digital Library

[5]

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, pages 184--193. IEEE, 1996.

Digital Library

[6]

R. D. Carr, L. K. Fleischer, V. J. Leung, and C. A. Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 106--115. SIAM, 2000.

Digital Library

[7]

S. Chechik, M. Langberg, D. Peleg, and L. Roditty. Fault-tolerant spanners for general graphs. In 41st Annual ACM Symposium on Theory of Computing, pages 435--444. ACM, 2009.

Digital Library

[8]

A. Czumaj and H. Zhao. Fault-tolerant geometric spanners. In Proceedings of the 19th Annual Symposium on Computational Geometry, pages 1--10. ACM, 2003.

Digital Library

[9]

B. Derbel, C. Gavoille, D. Peleg, and L. Viennot. On the locality of distributed sparse spanner construction. In 27th Annual ACM Symposium on Principles of Distributed Computing, pages 273--282. ACM, 2008.

Digital Library

[10]

M. Dinitz and R. Krauthgamer. Directed spanners via flow-based linear programs. In STOC, 2011. To appear.

Digital Library

[11]

D. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA, 2009.

Digital Library

[12]

M. Elkin, Y. Emek, D. A. Spielman, and S.-H. Teng. Lower-stretch spanning trees. SIAM J. Comput., 38(2):608--628, 2008.

Digital Library

[13]

M. Elkin and D. Peleg. The client-server 2-spanner problem with applications to network design. In 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 117--132, 2001.

[14]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485--497, 2004.

Digital Library

[15]

A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer Science, pages 534--543, October 2003.

Digital Library

[16]

R. Krauthgamer and J. R. Lee. The intrinsic dimensionality of graphs. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 438--447, June 2003.

Digital Library

[17]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. The price of being near-sighted. In 27th Annual ACM-SIAM symposium on Discrete Algorithm, pages 980--989. ACM, 2006.

Digital Library

[18]

G. Kortsarz. On the hardness of approximating spanners. Algorithmica, 30(3):432--450, 2001.

[19]

G. Kortsarz and D. Peleg. Generating sparse 2-spanners. J. Algorithms, 17(2):222--236, 1994.

Digital Library

[20]

P. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In 25th Annual ACM Symposium on Theory of Computing, pages 682--690, May 1993.

Digital Library

[21]

C. Levcopoulos, G. Narasimhan, and M. Smid. Efficient algorithms for constructing fault-tolerant geometric spanners. In 30th ACM Symposium on Theory of Computing, pages 186--195. ACM, 1998.

Digital Library

[22]

N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441--454, 1993.

[23]

T. Lukovszki. New results on fault tolerant geometric spanners. In Proceedings of the 6th International Workshop on Algorithms and Data Structures, WADS '99, pages 193--204, London, UK, 1999. Springer-Verlag.

Digital Library

[24]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[25]

R. A. Moser and G. Tardos. A constructive proof of the general Lovász Local Lemma. J. ACM, 57:11:1--11:15, February 2010.

Digital Library

[26]

D. Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000.

Digital Library

[27]

D. Peleg and A. A. Schaffer. Graph spanners. J. Graph Theory, 13(1):99--116, 1989.

[28]

D. Peleg and J. D. Ullman. An optimal synchronizer for the hypercube. SIAM J. Comput., 18:740--747, August 1989.

Digital Library

[29]

S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300--306. ACM, 1999.

Digital Library

[30]

D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In 36th Annual ACM Symposium on Theory of Computing, pages 81--90. ACM, 2004.

Digital Library

[31]

M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1--24, 2005.

Digital Library

[32]

O. Weimann and R. Yuster. Replacement paths via fast matrix multiplication. In 51st Annual IEEE Symposium on Foundations of Computer Science, pages 655--662, 2010.

Digital Library

Cited By

C. S. KParter M(2024)Deterministic Replacement Path CoveringACM Transactions on Algorithms10.1145/367376020:4(1-35)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3673760
Dinitz MKoranteng AKortsarz GNutov Z(2023)Improved Approximations for Relative Survivable Network DesignApproximation and Online Algorithms10.1007/978-3-031-49815-2_14(190-204)Online publication date: 22-Dec-2023
https://doi.org/10.1007/978-3-031-49815-2_14
Parter MLeonardi SGupta A(2022)Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallelProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520047(1080-1092)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520047
Show More Cited By

Index Terms

Fault-tolerant spanners: better and simpler
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

We (nearly) settle the time complexity for computing vertex fault-tolerant (VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs that preserve distance information, up to a small multiplicative stretch, ...
Efficient and Simple Algorithms for Fault-Tolerant Spanners
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

It was recently shown that a version of the greedy algorithm gives a construction of fault-tolerant spanners that is size-optimal, at least for vertex faults. However, the algorithm to construct this spanner is not polynomial-time, and the best-known ...
Fault-tolerant spanners for general graphs
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δ_H(u,v) ≤ k· δ_G(u,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

June 2011

406 pages

ISBN:9781450307192

DOI:10.1145/1993806

General Chair:
Cyril Gavoille
LaBRI, University of Bordeaux, France
,
Program Chair:
Pierre Fraigniaud
CNRS and University of Paris Diderot, France

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '11

Sponsor:

PODC '11: ACM Symposium on Principles of Distributed Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
318
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)3

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

C. S. KParter M(2024)Deterministic Replacement Path CoveringACM Transactions on Algorithms10.1145/367376020:4(1-35)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3673760
Dinitz MKoranteng AKortsarz GNutov Z(2023)Improved Approximations for Relative Survivable Network DesignApproximation and Online Algorithms10.1007/978-3-031-49815-2_14(190-204)Online publication date: 22-Dec-2023
https://doi.org/10.1007/978-3-031-49815-2_14
Parter MLeonardi SGupta A(2022)Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallelProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520047(1080-1092)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520047
Filtser ALe HLeonardi SGupta A(2022)Locality-sensitive orderings and applications to reliable spannersProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520042(1066-1079)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520042
Banerjee NGupta MRaman VSaurabh S(2022)Output Sensitive Fault Tolerant Maximum MatchingComputer Science – Theory and Applications10.1007/978-3-031-09574-0_8(115-132)Online publication date: 24-Jun-2022
https://doi.org/10.1007/978-3-031-09574-0_8
Braverman VJiang SKrauthgamer RWu XRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Coresets for clustering with missing valuesProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541589(17360-17372)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3541589
Bodwin GDinitz MRobelle CMarx D(2021)Optimal vertex fault-tolerant spanners in polynomial timeProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458238(2924-2938)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458238
Duan RGu YRen HMarx D(2021)Approximate distance oracles subject to multiple vertex failuresProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458212(2497-2516)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458212
Karthik CParter MMarx D(2021)Deterministic replacement path coveringProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458108(704-723)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458108
Jambulapati ASidford AMarx D(2021)Ultrasparse ultrasparsifiers and faster laplacian system solversProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458097(540-559)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458097
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents