Document Open Access Logo

Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages

Authors Sriram V. Pemmaraju, Vivek B. Sardeshmukh

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.47.pdf
  • Filesize: 0.63 MB
  • 15 pages

Document Identifiers

Author Details

Sriram V. Pemmaraju
Vivek B. Sardeshmukh

Cite As Get BibTex

Sriram V. Pemmaraju and Vivek B. Sardeshmukh. Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.47

Abstract

In a sequence of recent results (PODC 2015 and PODC 2016), the running time of the fastest algorithm for the minimum spanning tree (MST) problem in the Congested Clique model was first improved to O(log(log(log(n)))) from O(log(log(n))) (Hegeman et al., PODC 2015) and then to O(log^*(n)) (Ghaffari and Parter, PODC 2016). All of these algorithms use Theta(n^2) messages independent of the number of edges in the input graph.

This paper positively answers a question raised in Hegeman et al., and presents the first "super-fast" MST algorithm with o(m) message complexity for input graphs with m edges. Specifically, we present an algorithm running in O(log^*(n)) rounds, with message complexity ~O(sqrt{m * n}) and then build on this algorithm to derive a family of algorithms, containing for any epsilon, 0 < epsilon <= 1, an algorithm running in O(log^*(n)/epsilon) rounds, using ~O(n^{1 + epsilon}/epsilon) messages. Setting epsilon = log(log(n))/log(n) leads to the first sub-logarithmic round Congested Clique MST algorithm that uses only ~O(n) messages. 

Our primary tools in achieving these results are 

(i) a component-wise bound on the number of candidates for MST edges, extending the sampling lemma of Karger, Klein, and Tarjan (Karger, Klein, and Tarjan, JACM 1995) and 

(ii) Theta(log(n))-wise-independent linear graph sketches (Cormode and Firmani, Dist. Par. Databases, 2014) for generating MST candidate edges.

Subject Classification

Keywords
  • Congested Clique
  • Minimum Spanning Tree
  • Linear Graph Sketches
  • Message Complexity
  • Sampling

Metrics

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

References

  1. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the 23rd annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459-467, 2012. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st Symposium on Principles of Database Systems (PODS), pages 5-14, 2012. Google Scholar
  3. Andrew Berns, James Hegeman, and Sriram V. Pemmaraju. Super-Fast Distributed Algorithms for Metric Facility Location. In Proccedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pages 428-439, 2012. Google Scholar
  4. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21-23, 2015, pages 143-152. ACM, 2015. URL: http://dx.doi.org/10.1145/2767386.2767414.
  5. Graham Cormode and Donatella Firmani. A unifying framework for 𝓁₀-sampling algorithms. Distributed and Parallel Databases, 32(3):315-335, 2014. Google Scholar
  6. Danny Dolev, Christoph Lenzen, and Shir Peled. "Tri, Tri Again": Finding Triangles and Small Subgraphs in a Distributed Setting. In Proceedings of the 26th International Symposium on Distributed Computing (DISC), pages 195-209, 2012. Google Scholar
  7. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. The communication complexity of distributed task allocation. In Proceedings of the 30st ACM Symposium on Principles of Distributed Computing (PODC), pages 67-76, 2012. URL: http://dx.doi.org/10.1145/2332432.2332443.
  8. Michael Elkin. An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. SIAM J. Comput., 36(2):433-456, 2006. URL: http://dx.doi.org/10.1137/S0097539704441058.
  9. Joachim Gehweiler, Christiane Lammersen, and Christian Sohler. A Distributed O(1)-approximation Algorithm for the Uniform Facility Location Problem. In Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 237-243, 2006. URL: http://dx.doi.org/10.1145/1148109.1148152.
  10. Mohsen Ghaffari and Merav Parter. MST in Log-Star Rounds of Congested Clique. In Proc. of the 2016 ACM Symposium on Principles of Distributed Computing, PODC'16, 2016. Google Scholar
  11. James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC'15, pages 91-100. ACM, 2015. URL: http://dx.doi.org/10.1145/2767386.2767434.
  12. James W. Hegeman and Sriram V. Pemmaraju. Lessons from the Congested Clique Applied to MapReduce. In Proceedings of the 21th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 149-164, 2014. URL: http://dx.doi.org/10.1007/978-3-319-09620-9_13.
  13. James W. Hegeman, Sriram V. Pemmaraju, and Vivek B. Sardeshmukh. Near-Constant-Time Distributed Algorithms on a Congested Clique. In Proceedings of the 28th International Symposium on Distributed Computing (DISC), pages 514-530, 2014. Google Scholar
  14. Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. CoRR, abs/1412.3445, 2014. Google Scholar
  15. Hossein Jowhari, Mert Sağlam, and Gábor Tardos. Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems. In Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'11, pages 49-58. ACM, 2011. URL: http://dx.doi.org/10.1145/1989284.1989289.
  16. David R. Karger, Philip N. Klein, and Robert E. Tarjan. A Randomized Linear-time Algorithm to Find Minimum Spanning Trees. J. ACM, 42(2):321-328, March 1995. URL: http://dx.doi.org/10.1145/201019.201022.
  17. Valerie King, Shay Kutten, and Mikkel Thorup. Construction and impromptu repair of an mst in a distributed network with o(m) communication. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC'15, pages 71-80, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2767386.2767405.
  18. 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
  19. Janne H. Korhonen. Deterministic MST sparsification in the congested clique. CoRR, abs/1605.02022, 2016. URL: http://arxiv.org/abs/1605.02022.
  20. Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. On the complexity of universal leader election. J. ACM, 62(1):7:1-7:27, March 2015. URL: http://dx.doi.org/10.1145/2699440.
  21. Shay Kutten and David Peleg. Fast Distributed Construction of Small k-Dominating Sets and Applications. J. Algorithms, 28(1):40-66, 1998. URL: http://dx.doi.org/10.1006/jagm.1998.0929.
  22. Christoph Lenzen. Optimal Deterministic Routing and Sorting on the Congested Clique. In Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (PODC), pages 42-50. ACM, 2013. URL: http://dx.doi.org/10.1145/2484239.2501983.
  23. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds. SIAM Journal on Computing, 35(1):120-131, 2005. Google Scholar
  24. Andrew McGregor. Graph stream algorithms: A survey. ACM SIGMOD Record, 43(1):9-20, 2014. Google Scholar
  25. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995. Google Scholar
  26. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proc. of the 46th ACM Symp. on Theory of Computing (STOC), pages 565-573, 2014. Google Scholar
  27. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. A time- and message-optimal distributed algorithm for minimum spanning trees. CoRR, abs/1607.06883, 2016. URL: http://arxiv.org/abs/1607.06883.
  28. Boaz Patt-Shamir and Marat Teplitsky. The Round Complexity of Distributed Sorting. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 249-256, 2011. URL: http://dx.doi.org/10.1145/1993806.1993851.
  29. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial Mathematics, 2000. Google Scholar
  30. Sriram V. Pemmaraju and Vivek B. Sardeshmukh. Super-fast MST algorithms in the congested clique using o(m) messages. CoRR, abs/1610.03897, 2016. URL: http://arxiv.org/abs/1610.03897.
  31. Seth Pettie and Vijaya Ramachandran. Randomized minimum spanning tree algorithms using exponentially fewer random bits. ACM Trans. Algorithms, 4(1), 2008. URL: http://dx.doi.org/10.1145/1328911.1328916.
  32. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput., 41(5):1235-1265, 2012. Google Scholar
  33. Jeanette P. Schmidt, Alan Siegel, and Srinivasan Aravind. Chernoff-Hoeffding Bounds for Applications with Limited Independence. SIAM J. Discrete Math., 8(2):223-250, 1995. URL: http://dx.doi.org/10.1137/S089548019223872X.
  34. Robert Endre Tarjan. CBMS-NSF Regional Conference Series in Applied Mathematics: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, New York, NY, USA, 1983. 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 About DROPS Imprint Privacy Contact