research-article

Deterministic massively parallel connectivity

Authors:

Artur CzumajAuthors Info & Claims

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

Pages 162 - 175

https://doi.org/10.1145/3519935.3520055

Published: 10 June 2022 Publication History

Abstract

We consider the problem of designing fundamental graph algorithms on the model of Massive Parallel Computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only Θ(n^δ) words for an arbitrary constant δ>0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization.

In a recent breakthrough, Andoni et al. (FOCS’18) and Behnezhad et al. (FOCS’19) designed parallel randomized algorithms that in O(logD + loglogn) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O(logn) derived from earlier works on PRAM algorithms.

In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O(logD + loglogn) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc.

We complement our upper bounds by extending a recent lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires D ≥ log^1+Ω(1)n), by showing a related conditional hardness of Ω(logD) MPC rounds for the entire spectrum of D, covering a particularly interesting range when D ≤ O(logn).

References

[1]

Noga Alon and Joel H. Spencer. 2016. The Probabilistic Method (4th ed.). John Wiley & Sons, New York, NY. https://doi.org/10.1002/9780470277331

[2]

Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. 2014. Parallel Algorithms for Geometric Graph Problems. In 46th. ACM Press, New York, NY. 574–583. https://doi.org/10.1145/2591796.2591805

Digital Library

[3]

Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. 2018. Parallel Graph Connectivity in Log Diameter Rounds. In 59th. IEEE Computer Society Press, Los Alamitos, CA. 674–685. https://doi.org/10.1109/FOCS.2018.00070 Also in ASSWZ18a

[4]

Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, and Peilin Zhong. 2018. Parallel Graph Connectivity in Log Diameter Rounds. CoRR, arXiv, abs/1805.03055 (2018), Also in ASSWZ18

[5]

Alexandr Andoni, Clifford Stein, and Peilin Zhong. 2020. Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators. In 52nd. ACM Press, New York, NY. 322–335. https://doi.org/10.1145/3357713.3384321

Digital Library

[6]

Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. 2019. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. In 30th. SIAM, Philadelphia, PA. 1616–1635. https://doi.org/10.1137/1.9781611975482.98

[7]

Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. 2019. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. In 38th. ACM Press, New York, NY. 461–470. https://doi.org/10.1145/3293611.3331596

Digital Library

[8]

Philipp Bamberger, Fabian Kuhn, and Yannic Maus. 2020. Efficient Deterministic Distributed Coloring with Small Bandwidth. In 39th. ACM Press, New York, NY. 243–252. https://doi.org/10.1145/3382734.3404504

Digital Library

[9]

Paul Beame, Paraschos Koutris, and Dan Suciu. 2013. Communication Steps for Parallel Query Processing. In 32nd. ACM Press, New York, NY. 273–284. https://doi.org/10.1145/2463664.2465224

Digital Library

[10]

Paul Beame, Paraschos Koutris, and Dan Suciu. 2017. Communication Steps for Parallel Query Processing. J. ACM, 64, 6 (2017), 40:1–40:58. https://doi.org/10.1145/3125644

Digital Library

[11]

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 38th. ACM Press, New York, NY. 481–490. https://doi.org/10.1145/3293611.3331609

Digital Library

[12]

Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. 2018. Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR, arXiv, abs/1802.10297 (2018), https://doi.org/10.48550/arXiv.1802.10297

[13]

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab S. Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. In 60th. IEEE Computer Society Press, Los Alamitos, CA. 1615–1636. https://doi.org/10.1109/FOCS.2019.00095 Also in BDELM19a

[14]

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab S. Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. CoRR, arXiv, abs/1910.05385 (2019), Also in BDELM19

[15]

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Vahab S. Mirrokni, and Warren Schudy. 2019. Massively Parallel Computation via Remote Memory Access. In 31st. ACM Press, New York, NY. 59–68. https://doi.org/10.1145/3470631

Digital Library

[16]

Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. 2019. Exponentially Faster Massively Parallel Maximal Matching. In 60th. IEEE Computer Society Press, Los Alamitos, CA. 1637–1649. https://doi.org/10.1109/FOCS.2019.00096

[17]

Bonnie Berger, John Rompel, and Peter W. Shor. 1989. Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry. In 30th. IEEE Computer Society, Los Alamitos, CA. 54–59. https://doi.org/10.1109/SFCS.1989.63455

Digital Library

[18]

Sebastian Brandt, Rustam Latypov, and Jara Uitto. 2021. Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. In 35th. LIPIcs, Schloss Dagstuhl — Leibniz-Zentrum für Informatik. 50:1–50:4.

[19]

Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. 2017. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In 31st. 91, LIPIcs, Schloss Dagstuhl — Leibniz-Zentrum für Informatik. 11:1–11:16. https://doi.org/10.4230/LIPIcs.DISC.2017.11 Journal version appeared in CPS20

[20]

Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. 2020. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. Distributed Computing, 33, 3-4 (2020), 349–366. https://doi.org/10.1007/s00446-020-00376-1

Digital Library

[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 38th. ACM Press, New York, NY. 471–480.

[22]

Moses Charikar, Weiyun Ma, and Li-Yang Tan. 2021. Brief Announcement: A Randomness-Efficient Massively Parallel Algorithm for Connectivity. In 40th. ACM Press, New York, NY. 431–433. isbn:9781450385480 https://doi.org/10.1145/3465084.3467951

Digital Library

[23]

Ka Wong Chong, Yijie Han, and Tak Wah Lam. 2001. Concurrent Threads and Optimal Parallel Minimum Spanning Trees Algorithm. J. ACM, 48, 2 (2001), 297–323. https://doi.org/10.1145/375827.375847

Digital Library

[24]

Artur Czumaj, Peter Davies, and Merav Parter. 2020. Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space. In 32nd. ACM Press, New York, NY. 175–185.

[25]

Artur Czumaj, Peter Davies, and Merav Parter. 2020. Simple, Deterministic, Constant-Round Coloring in the Congested Clique. In 39th. ACM Press, New York, NY. 309–318.

[26]

Artur Czumaj, Peter Davies, and Merav Parter. 2021. Component Stability in Low-Space Massively Parallel Computations. In 40th. ACM Press, New York, NY. 481–491. isbn:9781450385480 https://doi.org/10.1145/3465084.3467903

Digital Library

[27]

Artur Czumaj, Peter Davies, and Merav Parter. 2021. Improved Deterministic (Δ + 1)-Coloring in Low-space MPC. In 40th. ACM Press, New York, NY. 469–479. isbn:9781450385480 https://doi.org/10.1145/3465084.3467937

Digital Library

[28]

Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. 2018. Round Compression for Parallel Matching Algorithms. In 50th. ACM Press, New York, NY. 471–484.

[29]

Andrzej Czygrinow, Michal Hańćkowiak, and Wojciech Wawrzyniak. 2008. Fast Distributed Approximations in Planar Graphs. In 22nd (Lecture Notes in Computer Science, Vol. 5218). Springer Verlag, Berlin, Heidelberg. 78–92.

Digital Library

[30]

Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: Simplified Data Processing on Large Clusters. Commun. ACM, 51, 1 (2008), January, 107–113. https://doi.org/10.1145/1327452.1327492

Digital Library

[31]

Janosch Deurer, Fabian Kuhn, and Yannic Maus. 2019. Deterministic Distributed Dominating Set Approximation in the CONGEST Model. In 38th. ACM Press, New York, NY. 94–103. https://doi.org/10.1145/3293611.3331626

Digital Library

[32]

Paul Erdös and John L. Selfridge. 1973. On a Combinatorial Game. Journal of Combinatorial Theory, Series A, 14, 3 (1973), 298–301.

[33]

Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Veličković. 1992. Approximations of General Independent Distributions. In 24th. ACM Press, New York, NY. 10–16. https://doi.org/10.1145/129712.129714

Digital Library

[34]

Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Veličković. 1998. Efficient Approximation of Product Distributions. 13, 1 (1998), 1–16. A preliminary version appeared in EGLNV92

[35]

Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. 2018. Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. In 37th. ACM Press, New York, NY. 129–138. https://doi.org/10.1145/3212734.3212743

Digital Library

[36]

Mohsen Ghaffari and Fabian Kuhn. 2018. Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In 32nd. LIPIcs, Schloss Dagstuhl — Leibniz-Zentrum für Informatik. 29:1–29:17.

[37]

Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. 2019. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In 60th. IEEE Computer Society Press, Los Alamitos, CA. 1650–1663.

[38]

Mohsen Ghaffari and Jara Uitto. 2019. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In 30th. SIAM, Philadelphia, PA. 1636–1653. https://doi.org/10.1137/1.9781611975482.99

[39]

Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, Searching, and Simulation in the MapReduce Framework. In 22nd (Lecture Notes in Computer Science, Vol. 7074). Springer Verlag, Berlin, Heidelberg. 374–383.

Digital Library

[40]

Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. 2007. Dryad: Distributed Data-parallel Programs from Sequential Building Blocks. SIGOPS Operating Systems Review, 41, 3 (2007), March, 59–72.

Digital Library

[41]

Tomasz Jurdziński and Krzysztof Nowicki. 2018. MST in O(1) Rounds of Congested Clique. In 29th. SIAM, Philadelphia, PA. 2620–2632. https://doi.org/10.1137/1.9781611975031.167

[42]

Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010. A Model of Computation for MapReduce. In 21st. SIAM, Philadelphia, PA. 938–948. https://doi.org/10.1137/1.9781611973075.76

[43]

Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. 2011. Filtering: A Method for Solving Graph Problems in MapReduce. In 23rd. ACM Press, New York, NY. 85–94. https://doi.org/10.1145/1989493.1989505

Digital Library

[44]

Christoph Lenzen and Roger Wattenhofer. 2008. Leveraging Linial’s Locality Limit. In 22nd (Lecture Notes in Computer Science, Vol. 5218). Springer Verlag, Berlin, Heidelberg. 394–407. https://doi.org/10.1007/978-3-540-87779-0_27

Digital Library

[45]

Sixue Cliff Liu, Robert E. Tarjan, and Peilin Zhong. 2020. Connected Components on a PRAM in Log Diameter Time. In 32nd. ACM Press, New York, NY. 359–369. https://doi.org/10.1145/3350755.3400249 A preliminary version appeared in LTZ20a

Digital Library

[46]

S. Cliff Liu, Robert E. Tarjan, and Peilin Zhong. 2020. Connected Components on a PRAM in Log Diameter Time. CoRR, arXiv, abs/2003.00614 (2020), Conference version appeared in LTZ20

[47]

Michael Luby. 1993. Removing Randomness in Parallel Computation without a Processor Penalty. J. Comput. System Sci., 47, 2 (1993), 250–286.

Digital Library

[48]

Rajeev Motwani, Joseph Naor, and Moni Naor. 1994. The Probabilistic Method Yields Deterministic Parallel Algorithms. J. Comput. System Sci., 49, 3 (1994), 478–516. https://doi.org/10.1016/S0022-0000(05)80069-8

Digital Library

[49]

Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press, New York, NY.

Digital Library

[50]

Danupon Nanongkai and Michele Scquizzato. 2022. Equivalence Classes and Conditional Hardness in Massively Parallel Computations. Distributed Computing, 35, 2 (2022), 165–183. https://doi.org/10.1007/s00446-021-00418-2

Digital Library

[51]

Krzysztof Nowicki. 2021. A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique. In 53rd. ACM, New York, NY. 1154–1165.

[52]

Krzysztof Onak. 2018. Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. CoRR, arXiv, abs/1807.08745 (2018).

[53]

Prabhakar Raghavan. 1988. Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs. J. Comput. System Sci., 37, 2 (1988), 130–143. https://doi.org/10.1016/0022-0000(88)90003-7

Digital Library

[54]

Tim Roughgarden, Sergei Vassilvitski, and Joshua R. Wang. 2018. Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation). J. ACM, 65, 6 (2018), Nov., 41:1–41:24.

Digital Library

[55]

Jukka Suomela. 2013. Survey of Local Algorithms. Comput. Surveys, 45, 2 (2013), Feb., 24:1–24:40. https://doi.org/10.1145/2431211.2431223

Digital Library

[56]

Tom White. 2015. Hadoop: The Definitive Guide: Storage and Analysis at Internet Scale (4th ed.). O’Reilly Media, Sebastopol, CA.

[57]

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). USENIX Association, Boston, MA.

[58]

Jakub Łącki, Vahab S. Mirrokni, and Michał Wł odarczyk. 2018. Connected Components at Scale via Local Contractions. CoRR, arXiv, abs/1807.10727 (2018).

[59]

Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. 2020. Walking Randomly, Massively, and Efficiently. In 52nd. ACM Press, New York, NY. 364–377.

Cited By

Giliberti JParsaeian ZKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Massively Parallel Ruling Set Made DeterministicProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662816(523-526)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662816
Coy SCzumaj AMishra GMukherjee AAgrawal KPetrank E(2024)Log Diameter Rounds MST Verification and Sensitivity in MPCProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659984(269-280)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659984
Farhadi ALiu SShi EAgrawal KPetrank E(2024)Connected Components in Linear Work and Near-Optimal TimeProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659963(395-402)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659963
Show More Cited By

Index Terms

Deterministic massively parallel connectivity
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Parallel algorithms
      1. Massively parallel algorithms
  2. Randomness, geometry and discrete structures
    1. Pseudorandomness and derandomization

Recommendations

Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

We consider the problem of designing deterministic graph algorithms for the model of Massively Parallel Computation (MPC) that improve with the sparsity of the input graph, as measured by the standard notion of arboricity. For the problems of maximal ...
Brief Announcement: Massively Parallel Ruling Set Made Deterministic
PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing

We study the deterministic complexity of the 2-Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local memory.

Linear MPC: We present a constant-round deterministic algorithm for the 2-Ruling Set ...
A deterministic algorithm for the MST problem in constant rounds of congested clique
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

In this paper we show that the Minimum Spanning Tree problem (MST) can be solved deterministically in O(1) rounds of the Congested Clique model.

In the Congested Clique model there are n players that perform computation in synchronous rounds. Each ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

June 2022

1698 pages

ISBN:9781450392648

DOI:10.1145/3519935

General Chair:
Stefano Leonardi
Sapienza University of Rome, Italy
,
Program Chair:
Anupam Gupta
Carnegie Mellon University, USA

Copyright © 2022 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '22

Sponsor:

SIGACT

STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing

June 20 - 24, 2022

Rome, Italy

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
152
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Giliberti JParsaeian ZKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Massively Parallel Ruling Set Made DeterministicProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662816(523-526)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662816
Coy SCzumaj AMishra GMukherjee AAgrawal KPetrank E(2024)Log Diameter Rounds MST Verification and Sensitivity in MPCProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659984(269-280)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659984
Farhadi ALiu SShi EAgrawal KPetrank E(2024)Connected Components in Linear Work and Near-Optimal TimeProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659963(395-402)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659963
Coy SCzumaj ADavies-Peck PMishra G(2024)Parallel Derandomization for Coloring*2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS57955.2024.00098(1058-1069)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPS57955.2024.00098

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents