Constant-Round Spanners and Shortest Paths in Congested Clique and MPC
Pages 223 - 233
Abstract
In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed CONGESTED CLIQUE model. Specifically, we show the following results for undirected n-node graphs. ulFor every integer k ≥ 1, O(1)-round algorithms for constructing O(k)-spanners with O(n1+1/k) edges in unweighted graphs, and O(k)-spanners with O(n1+1/k log n) edges in weighted graphs. An O(1)-round algorithm for O(log n)-approximation for APSP in unweighted graphs. An O(1)-round algorithm for O(log2n)-approximation for APSP in weighted graphs. All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O(k)-spanners in this model require poly(log k) rounds [Parter, Yogev, DISC '18] [Biswas et al., SPAA '21], and the fastest algorithms for approximate shortest paths require poly(log log n) rounds [Dory, Parter, PODC '20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O(1)-round algorithms for spanners and approximate shortest paths in this model as well.
Supplementary Material
PODC'21 conference presentation video
- Download
- 107.89 MB
References
[1]
Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. 1993. On sparse spanners of weighted graphs. Discrete & Computational Geometry, Vol. 9, 1 (1993), 81--100.
[2]
Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Michael Saks. 1992. Adapting to asynchronous dynamic networks. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing (STOC). 557--570.
[3]
Baruch Awerbuch and David Peleg. 1990. Network synchronization with polylogarithmic overhead. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS). 514--522.
[4]
Baruch Awerbuch and David Peleg. 1992. Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Mathematics, Vol. 5, 2 (1992), 151--162.
[5]
Surender Baswana. 2008. Streaming algorithm for graph spanners? single pass and constant processing time per edge. Inform. Process. Lett., Vol. 106, 3 (2008), 110--114.
[6]
Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. 2012. Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms (TALG), Vol. 8, 4 (2012), 1--51.
[7]
Surender Baswana and Sandeep Sen. 2006. Approximate distance oracles for unweighted graphs in expected O(n2) time. ACM Transactions on Algorithms (TALG), Vol. 2, 4 (2006), 557--577.
[8]
Surender Baswana and Sandeep Sen. 2007. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms, Vol. 30, 4 (2007), 532--563.
[9]
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31 International Symposium on Distributed Computing.
[10]
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. 2018. Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR, Vol. abs/1802.10297 (2018). arxiv: 1802.10297 http://arxiv.org/abs/1802.10297
[11]
Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari, Slobodan Mitrovic, and Yasamin Nazari. 2021. Massively Parallel Algorithms for Distance Approximation and Spanners. SPAA 2021 (2021).
[12]
Greg Bodwin and Sebastian Krinninger. 2016. Fully Dynamic Spanners with Worst-Case Update Time. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark. 17:1--17:18.
[13]
Keren Censor-Hillel and Michal Dory. 2018. Distributed spanner approximation. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 139--148.
[14]
Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. 2019. Fast Approximate Shortest Paths in the Congested Clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. 74--83.
[15]
Keren Censor-Hillel, Petteri Kaski, Janne H Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. 2019 a. Algebraic methods in the congested clique. Distributed Computing, Vol. 32, 6 (2019), 461--478.
[16]
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff. 2016. Distributed construction of purely additive spanners. In International Symposium on Distributed Computing (DISC). 129--142.
[17]
Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. 2019 b. Sparse matrix multiplication and triangle listing in the congested clique model. Theoretical Computer Science (2019).
[18]
Shiri Chechik. 2013. Compact routing schemes with improved stretch. In Proceedings of the 2013 ACM symposium on Principles of distributed computing (PODC). 33--41.
[19]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition 3rd ed.). The MIT Press.
[20]
Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified Data Processing on Large Clusters. In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI). USENIX Association, Berkeley, CA, USA, 10--10. http://dl.acm.org/citation.cfm?id=1251254.1251264
[21]
Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. 2008. On the locality of distributed sparse spanner construction. In Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (PODC). 273--282.
[22]
Michael Dinitz and Yasamin Nazari. 2017. Distributed Distance-Bounded Network Design Through Distributed Convex Programming. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017. 5:1--5:19.
[23]
Michael Dinitz and Yasamin Nazari. 2019. Massively Parallel Approximate Distance Sketches. In 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17-19, 2019, Neuchâ tel, Switzerland. 35:1--35:17.
[24]
Michal Dory and Merav Parter. 2020. Exponentially faster shortest paths in the congested clique. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC). 59--68.
[25]
Michael Elkin. 2005. Computing almost shortest paths. ACM Transactions on Algorithms (TALG), Vol. 1, 2 (2005), 283--323.
[26]
Michael Elkin. 2007. A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (PODC). 185--194.
[27]
Michael Elkin. 2011. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms (TALG), Vol. 7, 2 (2011), 1--17.
[28]
Michael Elkin and Shaked Matar. 2019. Near-additive spanners in low polynomial deterministic CONGEST time. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC). 531--540.
[29]
Michael Elkin and Ofer Neiman. 2018. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), Vol. 15, 1 (2018), 1--29.
[30]
Michael Elkin and Jian Zhang. 2004. Efficient algorithms for constructing (1+vε, β)-spanners in the distributed and streaming models. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing (PODC). 160--168.
[31]
Paul ErdHo s. 1964. Extremal problems in graph theory. In Theory Of Graphs And Its Applications, Proceedings of Symposium Smolenice. Publ. House Cszechoslovak Acad. Sci., Prague, 29--36.
[32]
Arnold Filtser, Michael Kapralov, and Navid Nouri. 2021. Graph spanners by sketching in dynamic streams and the simultaneous communication model. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1894--1913.
[33]
Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. 2019. Conditional hardness results for massively parallel computation from distributed lower bounds. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 1650--1663.
[34]
James W Hegeman and Sriram V Pemmaraju. 2015. Lessons from the congested clique applied to MapReduce. Theoretical Computer Science, Vol. 608 (2015), 268--281.
[35]
Stephan Holzer and Nathan Pinsker. 2016. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[36]
Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. 2007. Dryad: distributed data-parallel programs from sequential building blocks. In Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007. 59--72.
[37]
Taisuke Izumi and Francc ois Le Gall. 2019. Quantum distributed algorithm for the all-pairs shortest path problem in the congest-clique model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC). 84--93.
[38]
Michael Kapralov and David Woodruff. 2014. Spanners and sparsifiers in dynamic streams. In Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC). 272--281.
[39]
Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010. A model of computation for MapReduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 938--948.
[40]
Janne H. Korhonen. 2016. Deterministic MST Sparsification in the Congested Clique. CoRR, Vol. abs/1605.02022 (2016).
[41]
Francc ois Le Gall. 2016. Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In International Symposium on Distributed Computing. Springer, 57--70.
[42]
Christoph Lenzen. 2013. Optimal deterministic routing and sorting on the congested clique. In Proc. PODC 2013. 42--50.
[43]
Nathan Linial. 1992. Locality in Distributed Graph Algorithms. SIAM J. Comput., Vol. 21, 1 (1992), 193--201. https://doi.org/10.1137/0221015
[44]
Krzysztof Nowicki. 2021. A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique. STOC 2021 (2021).
[45]
Merav Parter and Eylon Yogev. 2018. Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018. 40:1-40:18.
[46]
David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
[47]
David Peleg and Alejandro A Schäffer. 1989. Graph spanners. Journal of graph theory, Vol. 13, 1 (1989), 99--116.
[48]
David Peleg and Jeffrey D Ullman. 1989. An optimal synchronizer for the hypercube. SIAM Journal on computing, Vol. 18, 4 (1989), 740--747.
[49]
David Peleg and Eli Upfal. 1989. A trade-off between space and efficiency for routing tables. Journal of the ACM (JACM), Vol. 36, 3 (1989), 510--530.
[50]
Seth Pettie. 2010. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing, Vol. 22, 3 (2010), 147--166.
[51]
Liam Roditty, Mikkel Thorup, and Uri Zwick. 2005. Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata, Languages, and Programming (ICALP). 261--272.
[52]
Mikkel Thorup and Uri Zwick. 2001. Compact routing schemes. In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures (SPAA). 1--10.
[53]
Tom White. 2012. Hadoop: The Definitive Guide. O'Reilly Media, Inc.
[54]
Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud). https://www.usenix.org/conference/hotcloud-10/spark-cluster-computing-working-sets
Index Terms
- Constant-Round Spanners and Shortest Paths in Congested Clique and MPC
Recommendations
Constant-Round Near-Optimal Spanners in Congested Clique
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed ComputingGraph spanners have been extensively studied in the literature of graph algorithms. In an undirected weighted graph G = (V, E,ω) on n vertices, a t-spanner of G is a subgraph that preserves pairwise distances up to a multiplicative stretch factor of t . ...
Fast Approximate Shortest Paths in the Congested Clique
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed ComputingWe design fast deterministic algorithms for distance computation in the CONGESTED CLIQUE model. Our key contributions include:
- A (2+ε)-approximation for all-pairs shortest paths problem in O(log2n / ε) rounds on unweighted undirected graphs. With a ...
Exponentially Faster Shortest Paths in the Congested Clique
We present improved deterministic algorithms for approximating shortest paths in the Congested Clique model of distributed computing. We obtain poly(log log n)-round algorithms for the following problems in unweighted undirected n-vertex graphs:
- ( 1 + ϵ)-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2021
590 pages
Copyright © 2021 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 the author(s) 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: 23 July 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- European Union's Horizon 2020 Research and Innovation Program
- Swiss National Foundation
- Defense Advanced Research Projects Agency (DARPA)
Conference
PODC '21: ACM Symposium on Principles of Distributed Computing
July 26 - 30, 2021
Virtual Event, Italy
Acceptance Rates
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 343Total Downloads
- Downloads (Last 12 months)40
- Downloads (Last 6 weeks)5
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in