Document Open Access Logo

Equivalence Classes and Conditional Hardness in Massively Parallel Computations

Authors Danupon Nanongkai, Michele Scquizzato

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.33.pdf
  • Filesize: 488 kB
  • 16 pages

Document Identifiers

Author Details

Danupon Nanongkai
  • KTH Royal Institute of Technology, Sweden
Michele Scquizzato
  • University of Padova, Italy

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 715672. M. Scquizzato was also partially supported by the University of Padova under grant BIRD197859/19.

Cite AsGet BibTex

Danupon Nanongkai and Michele Scquizzato. Equivalence Classes and Conditional Hardness in Massively Parallel Computations. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.33

Abstract

The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical graph problems. So far, the only way to argue lower bounds for this model is to condition on conjectures about the hardness of some specific problems, such as graph connectivity on promise graphs that are either one cycle or two cycles, usually called the one cycle vs. two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., P ≠ NP), which are often more robust in the sense that refuting them would lead to groundbreaking algorithms for a whole bunch of problems. In this paper we present connections between problems and classes of problems that allow the latter type of arguments. These connections concern the class of problems solvable in a sublogarithmic amount of rounds in the MPC model, denoted by MPC(o(log N)), and some standard classes concerning space complexity, namely L and NL, and suggest conjectures that are robust in the sense that refuting them would lead to many surprisingly fast new algorithms in the MPC model. We also obtain new conditional lower bounds, and prove new reductions and equivalences between problems in the MPC model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Massively parallel algorithms
Keywords
  • Massively parallel computation
  • conditional hardness
  • fine-grained complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Micah Adler, Wolfgang Dittrich, Ben H. H. Juurlink, Miroslaw Kutylowski, and Ingo Rieping. Communication-optimal parallel minimum spanning tree algorithms. In Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 27-36, 1998. Google Scholar
  2. Foto N. Afrati, Anish Das Sarma, Semih Salihoglu, and Jeffrey D. Ullman. Upper and Lower Bounds on the Cost of a Map-Reduce Computation. PVLDB, 6(4):277-288, 2013. Google Scholar
  3. Carme Àlvarez and Raymond Greenlaw. A compendium of problems complete for symmetric logarithmic space. Computational Complexity, 9(2):123-145, 2000. Google Scholar
  4. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the 46th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 574-583, 2014. Google Scholar
  5. Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, and Peilin Zhong. Parallel Graph Connectivity in Log Diameter Rounds. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 674-685, 2018. Google Scholar
  6. Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 14:1-14:16, 2019. Google Scholar
  7. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  8. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1616-1635, 2019. Google Scholar
  9. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear Algorithms for (Δ+1) Vertex Coloring. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 767-786, 2019. Google Scholar
  10. Sepehr Assadi and Sanjeev Khanna. Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2412-2431, 2018. Google Scholar
  11. Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 461-470, 2019. Google Scholar
  12. Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest Subgraph in Streaming and MapReduce. PVLDB, 5(5):454-465, 2012. Google Scholar
  13. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. J. ACM, 64(6), 2017. Google Scholar
  14. Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto. Massively Parallel Computation of Matching and MIS in Sparse Graphs. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 481-490, 2019. Google Scholar
  15. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Semi-MapReduce Meets Congested Clique. CoRR, abs/1802.10297, 2018. Google Scholar
  16. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab Mirrokni. Near-Optimal Massively Parallel Graph Connectivity. In Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2019. To appear. Google Scholar
  17. Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. Exponentially Faster Massively Parallel Maximal Matching. In Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2019. To appear. Google Scholar
  18. Gianfranco Bilardi, Michele Scquizzato, and Francesco Silvestri. A Lower Bound Technique for Communication in BSP. ACM Trans. Parallel Comput., 4(3):14:1-14:27, 2018. Google Scholar
  19. Ashok K. Chandra, Larry J. Stockmeyer, and Uzi Vishkin. Constant Depth Reducibility. SIAM J. Comput., 13(2):423-439, 1984. Google Scholar
  20. Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 471-480, 2019. Google Scholar
  21. Stephen A. Cook and Pierre McKenzie. Problems Complete for Deterministic Logarithmic Space. J. Algorithms, 8(3):385-394, 1987. Google Scholar
  22. Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 471-484, 2018. Google Scholar
  23. Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Commun. ACM, 51(1):107-113, 2008. Google Scholar
  24. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC), pages 367-376, 2014. Google Scholar
  25. Kousha Etessami. Counting Quantifiers, Successor Relations, and Logarithmic Space. J. Comput. Syst. Sci., 54(3):400-411, 1997. Google Scholar
  26. Benjamin Fish, Jeremy Kun, Ádám Dániel Lelkes, Lev Reyzin, and György Turán. On the Computational Complexity of MapReduce. In Proceedings of the 29th International Symposium on Distributed Computing (DISC), pages 1-15, 2015. Google Scholar
  27. Fabian Frei and Koichi Wada. Efficient Circuit Simulation in MapReduce. In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC), 2019. To appear. Google Scholar
  28. Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson. Weighted Matchings via Unweighted Augmentations. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 491-500, 2019. Google Scholar
  29. Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, and Ronitt Rubinfeld. Improved massively parallel computation algorithms for MIS, matching, and vertex cover. In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 129-138, 2018. Google Scholar
  30. Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2019. To appear. Google Scholar
  31. Mohsen Ghaffari and Jara Uitto. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1636-1653, 2019. Google Scholar
  32. Michael T. Goodrich. Communication-efficient parallel sorting. SIAM J. Comput., 29(2):416-432, 1999. Google Scholar
  33. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, Searching, and Simulation in the MapReduce Framework. In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC), pages 374-383, 2011. Google Scholar
  34. MohammadTaghi Hajiaghayi, Saeed Seddighin, and Xiaorui Sun. Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1654-1672, 2019. Google Scholar
  35. James W. Hegeman and Sriram V. Pemmaraju. Lessons from the Congested Clique applied to MapReduce. Theor. Comput. Sci., 608:268-281, 2015. Google Scholar
  36. Sungjin Im and Benjamin Moseley. A Conditional Lower Bound on Graph Connectivity in MapReduce. CoRR, abs/1904.08954, 2019. Google Scholar
  37. Sungjin Im, Benjamin Moseley, and Xiaorui Sun. Efficient massively parallel methods for dynamic programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 798-811, 2017. Google Scholar
  38. Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In Proceedings of the 2007 EuroSys Conference, pages 59-72, 2007. Google Scholar
  39. Riko Jacob, Tobias Lieber, and Nodari Sitchinava. On the Complexity of List Ranking in the Parallel External Memory Model. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 384-395, 2014. Google Scholar
  40. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In Proceedings of the 21st annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938-948, 2010. Google Scholar
  41. Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. Distributed Computation of Large-Scale Graph Problems. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 391-410, 2015. Google Scholar
  42. Janne H. Korhonen and Jukka Suomela. Towards a Complexity Theory for the Congested Clique. In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 163-172, 2018. Google Scholar
  43. Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani. Fast Greedy Algorithms in MapReduce and Streaming. ACM Trans. Parallel Comput., 2(3), 2015. Google Scholar
  44. Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Walking Randomly, Massively, and Efficiently. CoRR, abs/1907.05391, 2019. Google Scholar
  45. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in MapReduce. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 85-94, 2011. Google Scholar
  46. Harry R. Lewis and Christos H. Papadimitriou. Symmetric Space-Bounded Computation. Theor. Comput. Sci., 19:161-187, 1982. Google Scholar
  47. Philip D. MacKenzie and Vijaya Ramachandran. Computational bounds for fundamental problems on general-purpose parallel models. In Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 152-163, 1998. Google Scholar
  48. Krzysztof Onak. Personal communication, 2019. Google Scholar
  49. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. Fast Distributed Algorithms for Connectivity and MST in Large Graphs. ACM Trans. Parallel Comput., 5(1), 2018. Google Scholar
  50. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the Distributed Complexity of Large-Scale Graph Computations. In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 405-414, 2018. Google Scholar
  51. Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  52. Andrea Pietracaprina, Geppino Pucci, Matteo Riondato, Francesco Silvestri, and Eli Upfal. Space-round tradeoffs for MapReduce computations. In Proceedings of the 26th ACM International Conference on Supercomputing (ICS), pages 235-244, 2012. Google Scholar
  53. Vibhor Rastogi, Ashwin Machanavajjhala, Laukik Chitnis, and Anish Das Sarma. Finding connected components in Map-Reduce in logarithmic rounds. In Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE), pages 50-61, 2013. Google Scholar
  54. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1-17:24, 2008. Google Scholar
  55. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation). J. ACM, 65(6), 2018. Google Scholar
  56. Michele Scquizzato and Francesco Silvestri. Communication Lower Bounds for Distributed-Memory Computations. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), pages 627-638, 2014. Google Scholar
  57. Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997. Google Scholar
  58. Leslie G. Valiant. A Bridging Model for Parallel Computation. Commun. ACM, 33(8):103-111, 1990. Google Scholar
  59. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians 2018 (ICM 2018), pages 3431-3472, 2018. Google Scholar
  60. Tom White. Hadoop: The Definitive Guide. O'Reilly Media, Inc., 2012. Google Scholar
  61. Grigory Yaroslavtsev and Adithya Vadapalli. Massively parallel algorithms and hardness for single-linkage clustering under 𝓁_p-distances. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 5596-5605, 2018. Google Scholar
  62. Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J. Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. Apache Spark: a unified engine for big data processing. Commun. ACM, 59(11):56-65, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact