article

Distributed construction of purely additive spanners

Authors:

Keren Censor-Hillel,

Telikepalli Kavitha,

Amir YehudayoffAuthors Info & Claims

Distributed Computing, Volume 31, Issue 3

Pages 223 - 240

https://doi.org/10.1007/s00446-017-0306-2

Published: 01 June 2018 Publication History

Abstract

This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts. We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.

References

[1]

Abboud, A., Bodwin, G.: The 4/3 additive spanner exponent is tight. In: ACM SIGACT Symposium on Theory of Computing, STOC (2016)

Digital Library

[2]

Abboud, A., Bodwin, G.: Error amplification for pairwise spanner lower bounds. In: 27th Annual ACM---SIAM Symposium on Discrete Algorithms, SODA, pp. 841---854 (2016)

Digital Library

[3]

Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167---1181 (1999)

Digital Library

[4]

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

Digital Library

[5]

Baswana, S.: Streaming algorithm for graph spanners--single pass and constant processing time per edge. Inf. Process. Lett. 106(3), 110---114 (2008)

Digital Library

[6]

Baswana, S., Sarkar, S.: Fully dynamic algorithm for graph spanners with poly-logarithmic update time. In: 19th Annual ACM---SIAM Symposium on Discrete Algorithms, SODA, pp. 1125---1134 (2008)

Digital Library

[7]

Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30(4), 532---563 (2007)

Digital Library

[8]

Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and ($$\alpha, \beta $$?,ß)-spanners. ACM Trans. Algorithms 7(1), 5 (2010)

Digital Library

[9]

Baswana, S., Khurana, S., Sarkar, S.: Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms 8(4), 35 (2012)

Digital Library

[10]

Bodwin, G., Williams, V.V.: Better distance preservers and additive spanners. In: 27th Annual ACM---SIAM Symposium on Discrete Algorithms, SODA, pp. 855---872 (2016)

Digital Library

[11]

Bollobás, B., Coppersmith, D., Elkin, M.: Sparse distance preservers and additive spanners. SIAM J. Discrete Math. 19(4), 1029---1055 (2005)

Digital Library

[12]

Censor-Hillel, K., Ghaffari, M., Kuhn, F.: Distributed connectivity decomposition. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 156---165 (2014)

Digital Library

[13]

Censor-Hillel, K., Haeupler, B., Kelner, J.A., Maymounkov, P.: Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In: 44th Symposium on Theory of Computing Conference, STOC, pp. 961---970 (2012)

Digital Library

[14]

Censor-Hillel, K., Kavitha, T., Paz, A., Yehudayoff, A.: Distributed construction of purely additive spanners. In: 30th International Symposium on Distributed Computing, DISC, pp. 129---142 (2016)

[15]

Chechik, S.: Compact routing schemes with improved stretch. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 33---41 (2013)

Digital Library

[16]

Chechik, S.: New additive spanners. In: 24th Annual ACM---SIAM Symposium on Discrete Algorithms, SODA, pp. 498---512 (2013)

Digital Library

[17]

Coppersmith, D., Elkin, M.: Sparse sourcewise and pairwise distance preservers. SIAM J. Discrete Math. 20(2), 463---501 (2006)

Digital Library

[18]

Cygan, M., Grandoni, F., Kavitha, T.: On pairwise spanners. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS, pp. 209---220 (2013)

[19]

Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235---1265 (2012)

[20]

Derbel, B., Gavoille, C.: Fast deterministic distributed algorithms for sparse spanners. Theor. Comput. Sci. 399(1---2), 83---100 (2008)

Digital Library

[21]

Derbel, B., Gavoille, C., Peleg, D.: Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In: 21st International Symposium on Distributed Computing, DISC, pp. 179---192 (2007)

Digital Library

[22]

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

Digital Library

[23]

Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: Local computation of nearly additive spanners. In: 23rd International Symposium on Distributed Computing, DISC, pp. 176---190 (2009)

Digital Library

[24]

Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29(5), 1740---1759 (2000)

Digital Library

[25]

Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 367---376 (2014)

Digital Library

[26]

Dubhashi, D.P., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J. Comput. Syst. Sci. 71(4), 467---479 (2005)

Digital Library

[27]

Elkin, M.: Computing almost shortest paths. ACM Trans. Algorithms 1(2), 283---323 (2005)

Digital Library

[28]

Elkin, M.: A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In: 26th Annual ACM Symposium on Principles of Distributed Computing, PODC, pp. 185---194 (2007)

Digital Library

[29]

Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In: 34th International Colloquium on Automata, Languages and Programming, ICALP, pp. 716---727 (2007)

Digital Library

[30]

Elkin, M., Peleg, D.: ($$1+\epsilon, \beta $$1+∈,ß)-spanner constructions for general graphs. SIAM J. Comput. 33(3), 608---631 (2004)

Digital Library

[31]

Elkin, M., Zhang, J.: Efficient algorithms for constructing $$(1+\epsilon,\beta )$$(1+∈,ß)-spanners in the distributed and streaming models. Distrib. Comput. 18(5), 375---385 (2006)

Digital Library

[32]

Erd's, P.: Extremal problems in graph theory. In: Theory of Graphs and Its Applications: Proceedings of the Symposium Held in Smolenice in June 1963, pp. 29---36. Pub. House of the Czechoslovak Academy of Sciences (1964)

[33]

Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: 23rd Annual ACM---SIAM Symposium on Discrete Algorithms, SODA, pp. 1150---1162 (2012)

Digital Library

[34]

Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: 27th International Symposium on Distributed Computing, DISC, pp. 1---15 (2013)

Digital Library

[35]

Holzer, S., Pinsker, N.: Approximation of distances and shortest paths in the broadcast congest clique. CoRR, abs/1412.3445 (2014)

[36]

Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 355---364 (2012)

Digital Library

[37]

Kavitha, T.: New pairwise spanners. In: 32nd International Symposium on Theoretical Aspects of Computer Science, STACS, pp. 513---526 (2015)

[38]

Kavitha, T., Varma, N.M.: Small stretch pairwise spanners. In: 40th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 601---612 (2013)

Digital Library

[39]

Knudsen, M.B.T.: Additive spanners: A simple construction. In: 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, pp. 277---281 (2014)

[40]

Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)

Digital Library

[41]

Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 375---382 (2013)

Digital Library

[42]

Matousek, J.: Lectures on Discrete Geometry. Springer, New York (2002)

Digital Library

[43]

Mitzenmacher, M., Upfal, E.: Probability and Computing-Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)

Digital Library

[44]

Parter, M.: Bypassing erd's' girth conjecture: Hybrid stretch and sourcewise spanners. In: 41st International Colloquium on Automata, Languages, and Programming, ICALP, pp. 608---619 (2014)

[45]

Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)

Digital Library

[46]

Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed MST construction. In: 40th Annual Symposium on Foundations of Computer Science, FOCS, pp. 253---261 (1999)

Digital Library

[47]

Peleg, D., Schäffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99---116 (1989)

[48]

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

Digital Library

[49]

Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510---530 (1989)

Digital Library

[50]

Peleg, D., Roditty, L., Tal, E.: Distributed algorithms for network diameter and girth. In: Automata, Languages, and Programming--39th International Colloquium, ICALP, pp. 660---672 (2012)

Digital Library

[51]

Pettie, S.: Low distortion spanners. ACM Trans. Algorithms 6(1), 7:1---7:22 (2009)

Digital Library

[52]

Pettie, S.: Distributed algorithms for ultrasparse spanners and linear size skeletons. Distrib. Comput. 22(3), 147---166 (2010)

Digital Library

[53]

Roditty, L., Zwick, U.: On dynamic shortest paths problems. Algorithmica 61(2), 389---401 (2011)

Digital Library

[54]

Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: 32nd International Colloquium on Automata, Languages and Programming, ICALP, pp. 261---272 (2005)

Digital Library

[55]

Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, pp. 1---10 (2001)

Digital Library

[56]

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

Digital Library

[57]

Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: 17th Annual ACM---SIAM Symposium on Discrete Algorithms, SODA, pp. 802---809 (2006)

Digital Library

[58]

Woodruff, D.P.: Additive spanners in nearly quadratic time. In: 37th International Colloquium on Automata, Languages and Programming, ICALP, pp. 463---474 (2010)

Digital Library

Cited By

Zhu C(2023)Communication-Efficient Distributed Graph Clustering and Sparsification Under Duplication ModelsAlgorithms and Complexity10.1007/978-3-031-30448-4_27(383-398)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_27
Bezdrighin MElkin MGhaffari MGrunau CHaeupler BIlchi SRozhoň VAgrawal KLee I(2022)Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity CertificatesProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538565(1-10)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538565
Abboud ACensor-Hillel KKhoury SPaz A(2021)Smaller Cuts, Higher Lower BoundsACM Transactions on Algorithms10.1145/346983417:4(1-40)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3469834

Distributed construction of purely additive spanners
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

New additive spanners
SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms

This paper considers additive and purely additive spanners. We present a new purely additive spanner of size Õ(n^7/5) with additive stretch 4. This construction fills in the gap between the two existing constructions for purely additive spanners, one for ...
Weighted Additive Spanners
Graph-Theoretic Concepts in Computer Science
Abstract
A spanner of a graph G is a subgraph H that approximately preserves shortest path distances in G. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can ... $^{}$ $^{}$ $^{}$ $^{}$ $^{}$ $^{}$
Fault tolerant additive spanners
WG'12: Proceedings of the 38th international conference on Graph-Theoretic Concepts in Computer Science

Graph spanners are sparse subgraphs that preserve the distances of the original graph, up to some small multiplicative factor or additive term (known as the stretch of the spanner). A number of algorithms are known for constructing sparse spanners with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 31, Issue 3

June 2018

87 pages

ISSN:0178-2770

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer-Verlag GmbH Germany, part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 2018

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu C(2023)Communication-Efficient Distributed Graph Clustering and Sparsification Under Duplication ModelsAlgorithms and Complexity10.1007/978-3-031-30448-4_27(383-398)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_27
Bezdrighin MElkin MGhaffari MGrunau CHaeupler BIlchi SRozhoň VAgrawal KLee I(2022)Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity CertificatesProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538565(1-10)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538565
Abboud ACensor-Hillel KKhoury SPaz A(2021)Smaller Cuts, Higher Lower BoundsACM Transactions on Algorithms10.1145/346983417:4(1-40)Online publication date: 31-Oct-2021
https://dl.acm.org/doi/10.1145/3469834

View Options

View options

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents