Cited By
View all- Filtser ANeiman O(2022)Light Spanners for High Dimensional Norms via Stochastic DecompositionsAlgorithmica10.1007/s00453-022-00994-084:10(2987-3007)Online publication date: 1-Oct-2022
Massively Parallel Algorithms for Distance Approximation and Spanners
Authors: 
Amartya Shankha Biswas, Michal Dory, 
Mohsen Ghaffari, Slobodan Mitrović, Yasamin NazariAuthors Info & Claims
Pages 118 - 128
Abstract
Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms---usually sublogarithmic-time and often poly(łogłog n)-time, or even faster---for a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widely-adopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an all-to-all manner to process large-scale data. Contributing to this line of work on MPC graph algorithms, we present poly(łog k) ε poly(łogłog n) round MPC algorithms for computing O(k^1+o(1) )-spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for spanner construction.
As primary applications of our spanners, we get two important implications, as follows: -For the MPC setting, we get an O(łog^2łog n)-round algorithm for O(łog^1+o(1) n) approximation of all pairs shortest paths (APSP) in the near-linear regime of local memory. To the best of our knowledge, this is the first sublogarithmic-time MPC algorithm for distance approximations. -Our result above also extends to the Congested Clique model of distributed computing, with the same round complexity and approximation guarantee. This gives the first sub-logarithmic algorithm for approximating APSP in weighted graphs in the Congested Clique model.
References
[1]
Kook Jin Ahn and Sudipto Guha. 2015. Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching Under Resource Constraints. In SPAA. 202--211.
[2]
K. J. Ahn, S. Guha, and A. McGregor. 2012. Analyzing graph structure via linear measurements. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 459--467.
[3]
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. 2014. Parallel Algorithms for Geometric Graph Problems. In Proc. Symposium on Theory of Computation (STOC). 574--583.
[4]
Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, and Peilin Zhong. 2018. Parallel Graph Connectivity in Log Diameter Rounds. In Proc. Foundations of Computer Science (FOCS). 674--685.
[5]
Alexandr Andoni, Clifford Stein, and Peilin Zhong. 2019. Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. In Proc. ICALP, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.), Vol. 132. 14:1--14:16.
[6]
Alexandr Andoni, Clifford Stein, and Peilin Zhong. 2020. Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators. In Proc. Symposium on Theory of Computation (STOC).
[7]
Sepehr Assadi. 2017. Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599 (2017).
[8]
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. 2019. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. In Proc. Symposium on Discrete Algorithms (SODA), Timothy M. Chan (Ed.). 1616--1635.
[9]
Sepehr Assadi, Yu Chen, and Sanjeev Khanna. 2019. Sublinear Algorithms for ( + 1) Vertex Coloring. In Proceedings 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).
[10]
Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. 2019. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. In Proc. Principles of Distributed Computing (PODC), Peter Robinson and Faith Ellen (Eds.). 461--470.
[11]
Surender Baswana and Sandeep Sen. 2007. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms 30, 4 (2007), 532--563.
[12]
Paul Beame, Paraschos Koutris, and Dan Suciu. 2013. Communication Steps for Parallel Query Processing. In Proceedings of the 32Nd ACM SIGMOD-SIGACTSIGAI Symposium on Principles of Database Systems (PODS). 273--284.
[13]
Paul Beame, Paraschos Koutris, and Dan Suciu. 2014. Skew in Parallel Query Processing. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 212--223.
[14]
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In Proc. Symposium on DIStributed Computing (DISC), Vol. 91. 7:1--7:16.
[15]
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto. 2019. Massively Parallel Computation of Matching and MIS in Sparse Graphs. In Proc. Principles of Distributed Computing (PODC), Peter Robinson and Faith Ellen (Eds.). 481--490.
[16]
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab S. Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. In Proc. Foundations of Computer Science (FOCS), David Zuckerman (Ed.). 1615--1636.
[17]
Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. 2019. Exponentially Faster Massively Parallel Maximal Matching. In Proc. Foundations of Computer Science (FOCS), David Zuckerman (Ed.). 1637--1649.
[18]
Uri Ben-Levy and Merav Parter. 2020. New (, ) Spanners and Hopsets. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1695--1714.
[19]
Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin. 2018. Approximating edit distance in truly subquadratic time: quantum and MapReduce. In Proc. Symposium on Discrete Algorithms (SODA). 1170--1189.
[20]
Sebastian Brandt, Manuela Fischer, and Jara Uitto. 2018. Breaking the LinearMemory Barrier in MPC: Fast MIS on Trees with Memory per Machine. arXiv preprint arXiv:1802.06748 (2018).
[21]
Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. 2019. The Complexity of (+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. In Proc. Principles of Distributed Computing (PODC). 471--480.
[22]
Edith Cohen. 2000. Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM) 47, 1 (2000), 132--166.
[23]
Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. 2018. Round Compression for Parallel Matching Algorithms. In Proc. Symposium on Theory of Computation (STOC). 471--484.
[24]
Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: simplified data processing on large clusters. Commun. ACM 51, 1 (2008), 107--113.
[25]
Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. 2008. On the locality of distributed sparse spanner construction. In Proc. Principles of Distributed Computing (PODC). 273--282.
[26]
Michael Dinitz and Yasamin Nazari. 2019. Massively Parallel Approximate Distance Sketches. In Proceedings of International Conference on Principles of Distributed Systems (OPODIS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[27]
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.
[28]
Stephan Friedrichs and Christoph Lenzen. 2018. Parallel metric tree embedding based on an algebraic view on moore-bellman-ford. Journal of the ACM (JACM) 65, 6 (2018), 43.
[29]
Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson. 2019. Weighted Matchings via Unweighted Augmentations. In Proc. Principles of Distributed Computing (PODC), Peter Robinson and Faith Ellen (Eds.). ACM, 491--500.
[30]
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. [n.d.]. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In PODC vfill .
[31]
Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. 2019. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In Proc. Foundations of Computer Science (FOCS). IEEE Computer Society, 1650--1663.
[32]
Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic. 2019. Improved Parallel Algorithms for Density-Based Network Clustering. In Proceedings of the International Conference on Machine Learning (ICML), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 2201--2210.
[33]
Mohsen Ghaffari and Krzysztof Nowicki. 2020. Massively Parallel Algorithms for Minimum Cut. In Proc. Principles of Distributed Computing (PODC). to appear.
[34]
Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. 2020. Faster Algorithms for Edge Connectivity via Random 2-Out Contractions. In Proc. Symposium on Discrete Algorithms (SODA). 1260--1279.
[35]
Mohsen Ghaffari and Jara Uitto. 2019. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In Proc. Symposium on Discrete Algorithms (SODA). 1636--1653.
[36]
Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, searching, and simulation in the MapReduce framework. In Proc. ISAAC. Springer, 374--383.
[37]
MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin, and Cliff Stein. 2019. MapReduce meets fine-grained complexity: MapReduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond. arXiv preprint arXiv:1905.01748 (2019).
[38]
Nicholas J. A. Harvey, Christopher Liaw, and Paul Liu. 2018. Greedy and Local Ratio Algorithms in the MapReduce Model. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA) (Vienna, Austria). ACM, New York, NY, USA, 43--52. https://doi.org/10.1145/3210377.3210386
[39]
James W Hegeman and Sriram V Pemmaraju. 2015. Lessons from the congested clique applied to MapReduce. Theoretical Computer Science 608 (2015), 268--281.
[40]
Sungjin Im, Benjamin Moseley, and Xiaorui Sun. 2017. Efficient Massively Parallel Methods for Dynamic Programming. In Proc. Symposium on Theory of Computation (STOC). 798--811.
[41]
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.
[42]
Giuseppe F. Italiano, Silvio Lattanzi, Vahab S. Mirrokni, and Nikos Parotsidis. 2019. Dynamic Algorithms for the Massively Parallel Computation Model. In SPAA. 49--58.
[43]
Michael Kapralov and David Woodruff. 2014. Spanners and sparsifiers in dynamic streams. In Proceedings of the 2014 ACM symposium on Principles of distributed computing. 272--281.
[44]
Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010. A model of computation for MapReduce. In Proc. Symposium on Discrete Algorithms (SODA). 938--948.
[45]
Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. 2020. Walking Randomly, Massively, and Efficiently. In Proc. Symposium on Theory of Computation (STOC).
[46]
Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. 2011. Filtering: a method for solving graph problems in MapReduce. In SPAA. 85--94.
[47]
Jason Li. 2020. Faster Parallel Algorithm for Approximate Shortest Path. In Proc. Symposium on Theory of Computation (STOC).
[48]
Gary L Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. 2015. Improved parallel algorithms for spanners and hopsets. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures. 192--201.
[49]
Merav Parter and Eylon Yogev. 2018. Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[50]
David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.
[51]
David Peleg and Alejandro A Schäffer. 1989. Graph spanners. Journal of graph theory 13, 1 (1989), 99--116.
[52]
Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. 2016. Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation). In SPAA. 1--12.
[53]
Vaclav Rozhon and Mohsen Ghaffari. 2020. Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. In Proc. Symposium on Theory of Computation (STOC).
[54]
Tom White. 2012. Hadoop: The definitive guide. " O'Reilly Media, Inc.".
[55]
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
- Massively Parallel Algorithms for Distance Approximation and Spanners
Recommendations
Constant-Round Spanners and Shortest Paths in Congested Clique and MPC
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed ComputingIn 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 ...
Small Stretch Pairwise Spanners and Approximate $D$-Preservers
Let $G = (V,E)$ be an undirected unweighted graph on $n$ vertices. A subgraph $H$ of $G$ is called a purely additive spanner of $G$ with stretch $\beta$ if for each $(u,v) \in V \times V$, the $u$-$v$ distance in $H$ is at most $\delta_G(u,v) + \beta$. We ...
Sparse Distance Preservers and Additive Spanners
For an unweighted graph $G = (V,E)$, $G' = (V,E')$ is a subgraph if $E' \subseteq E$, and $G'' = (V'',E'',\omega)$ is a Steiner graph if $V \subseteq V''$, and for any pair of vertices $u,w \in V$, the distance between them in $G''$ (denoted $d_{G''}(...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2021
463 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 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
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- SIGARCH: ACM Special Interest Group on Computer Architecture
- EATCS: European Association for Theoretical Computer Science
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 06 July 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- European Research Council
- Swiss NSF
- NSF (National Science Foundation)
- Fintech@CSAIL
- MIT-IBM Watson AI Lab and Research Collaboration
Conference
SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures
July 6 - 8, 2021
Virtual Event, USA
Acceptance Rates
Overall Acceptance Rate 447 of 1,461 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 317Total Downloads
- Downloads (Last 12 months)101
- Downloads (Last 6 weeks)31
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
Cited By
View all- Filtser ANeiman O(2022)Light Spanners for High Dimensional Norms via Stochastic DecompositionsAlgorithmica10.1007/s00453-022-00994-084:10(2987-3007)Online publication date: 1-Oct-2022
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.
Sign in