Document Open Access Logo

The Complexity of Symmetry Breaking in Massive Graphs

Authors Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2019.26.pdf
  • Filesize: 0.64 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • communication complexity
  • information theory
  • k-machine model
  • maximal independent set
  • ruling set
  • streaming algorithms

Metrics

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

Abstract

The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related beta-ruling set problem, in two computational models suited for large-scale graph processing, namely the k-machine model and the graph streaming model. We present a number of results. For MIS in the k-machine model, we improve the O~(m/k^2 + Delta/k)-round upper bound of Klauck et al. (SODA 2015) by presenting an O~(m/k^2)-round algorithm. We also present an Omega~(n/k^2) round lower bound for MIS, the first lower bound for a symmetry breaking problem in the k-machine model. For beta-ruling sets, we use hierarchical sampling to obtain more efficient algorithms in the k-machine model and also in the graph streaming model. More specifically, we obtain a k-machine algorithm that runs in O~(beta n Delta^{1/beta}/k^2) rounds and, by using a similar hierarchical sampling technique, we obtain one-pass algorithms for both insertion-only and insertion-deletion streams that use O(beta * n^{1+1/2^{beta-1}}) space. The latter result establishes a clear separation between MIS, which is known to require Omega(n^2) space (Cormode et al., ICALP 2019), and beta-ruling sets, even for beta = 2. Finally, we present an even faster 2-ruling set algorithm in the k-machine model, one that runs in O~(n/k^{2-epsilon} + k^{1-epsilon}) rounds for any epsilon, 0 <=epsilon <=1. For a wide range of values of k this round complexity simplifies to O~(n/k^2) rounds, which we conjecture is optimal.
Our results use a variety of techniques. For our upper bounds, we prove and use simulation theorems for beeping algorithms, hierarchical sampling, and L_0-sampling, whereas for our lower bounds we use information-theoretic arguments and reductions to 2-party communication complexity problems.

Cite As Get BibTex

Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. The Complexity of Symmetry Breaking in Massive Graphs. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.DISC.2019.26

Author Details

Christian Konrad
  • Department of Computer Science, University of Bristol, Bristol BS8 1UB, UK
Sriram V. Pemmaraju
  • Department of Computer Science, The University of Iowa, Iowa City, IA 52242, USA
Talal Riaz
  • Department of Computer Science, The University of Iowa, Iowa City, IA 52242, USA
Peter Robinson
  • Department of Computer Science, City University of Hong Kong

References

  1. Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, and Ziv Bar-Joseph. A Biological Solution to a Fundamental Distributed Computing Problem. Science, 331(6014):183-185, 2011. URL: https://doi.org/10.1126/science.1193210.
  2. Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation Clustering in Data Streams. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, pages 2237-2246, 2015. URL: http://proceedings.mlr.press/v37/ahn15.html.
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing Graph Structure via Linear Measurements. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 459-467, Philadelphia, PA, USA, 2012. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2095116.2095156.
  4. Noga Alon, László Babai, and Alon Itai. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms, 7(4):567-583, 1986. Google Scholar
  5. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear Algorithms for (Δ + 1) Vertex Coloring. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 767-786, 2019. URL: https://doi.org/10.1137/1.9781611975482.48.
  6. Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. A Trade-Off between Information and Communication in Broadcast Protocols. J. ACM, 37(2):238-256, 1990. URL: https://doi.org/10.1145/77600.77618.
  7. Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, and Sriram V. Pemmaraju. Near-Optimal Clustering in the k-machine model. In Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018, Varanasi, India, January 4-7, 2018, pages 15:1-15:10, 2018. URL: https://doi.org/10.1145/3154273.3154317.
  8. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004. URL: https://doi.org/10.1016/j.jcss.2003.11.006.
  9. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The Locality of Distributed Symmetry Breaking. J. ACM, 63(3):20:1-20:45, June 2016. URL: https://doi.org/10.1145/2903137.
  10. Tushar Bisht, Kishore Kothapalli, and Sriram V. Pemmaraju. Brief announcement: Super-fast t-ruling sets. In ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 379-381, 2014. URL: https://doi.org/10.1145/2611462.2611512.
  11. Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan. One Trillion Edges: Graph Processing at Facebook-scale. Proc. VLDB Endow., 8(12):1804-1815, August 2015. URL: https://doi.org/10.14778/2824032.2824077.
  12. Graham Cormode, Jacques Dark, and Christian Konrad. Independent Sets in Vertex-Arrival Streams. In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019), Patras, Greece, 2019. to appear. Google Scholar
  13. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. URL: http://www.cambridge.org/gb/knowledge/isbn/item2327542/.
  14. Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 270-277, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch20.
  15. Mohsen Ghaffari. Distributed Maximal Independent Set using Small Messages. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 805-820, 2019. URL: https://doi.org/10.1137/1.9781611975482.50.
  16. 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 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 129-138, 2018. URL: https://doi.org/10.1145/3212734.3212743.
  17. Mohsen Ghaffari and Jara Uitto. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1636-1653, 2019. URL: https://doi.org/10.1137/1.9781611975482.99.
  18. Seth Gilbert and Calvin Newport. The Computational Power of Beeps. In Yoram Moses, editor, Distributed Computing, pages 31-46, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. Google Scholar
  19. Monika R. Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. Computing on Data Streams. In James M. Abello and Jeffrey Scott Vitter, editors, External Memory Algorithms, pages 107-118. American Mathematical Society, Boston, MA, USA, 1999. URL: http://dl.acm.org/citation.cfm?id=327766.327782.
  20. Tanmay Inamdar, Shreyas Pai, and Sriram V. Pemmaraju. Large-Scale Distributed Algorithms for Facility Location with Outliers. In 22nd International Conference on Principles of Distributed Systems, OPODIS 2018, December 17-19, 2018, Hong Kong, China, pages 5:1-5:16, 2018. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2018.5.
  21. Peter Jeavons, Alex Scott, and Lei Xu. Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring. Distributed Computing, 29(5):377-393, 2016. URL: https://doi.org/10.1007/s00446-016-0269-8.
  22. 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, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1989284.1989289.
  23. Tomasz Jurdziński and Krzysztof Nowicki. MST in O(1) Rounds of Congested Clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 2620-2632, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3174304.3175472.
  24. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 938-948, 2010. URL: https://doi.org/10.1137/1.9781611973075.76.
  25. Majid Khabbazian, Dariusz R. Kowalski, Fabian Kuhn, and Nancy Lynch. Decomposing broadcast algorithms using abstract MAC layers. Ad Hoc Networks, 12:219-242, 2014. URL: https://doi.org/10.1016/j.adhoc.2011.12.001.
  26. Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. Distributed Computation of Large-scale Graph Problems. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, pages 391-410, Philadelphia, PA, USA, 2015. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2722129.2722157.
  27. Kishore Kothapalli and Sriram V. Pemmaraju. Super-Fast 3-Ruling Sets. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, pages 136-147, 2012. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2012.136.
  28. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local Computation: Lower and Upper Bounds. J. ACM, 63(2):17:1-17:44, March 2016. URL: https://doi.org/10.1145/2742012.
  29. M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set. SIAM Journal on Computing, 15:1036-1053, 1986. Google Scholar
  30. Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: A System for Large-scale Graph Processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD '10, pages 135-146, New York, NY, USA, 2010. ACM. URL: https://doi.org/10.1145/1807167.1807184.
  31. Andrew McGregor. Graph Stream Algorithms: A Survey. SIGMOD Rec., 43(1):9-20, May 2014. URL: https://doi.org/10.1145/2627692.2627694.
  32. S. Muthukrishnan. Data Streams: Algorithms and Applications. Found. Trends Theor. Comput. Sci., 1(2):117-236, August 2005. URL: https://doi.org/10.1561/0400000002.
  33. Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. Brief Announcement: Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets. In Andréa W. Richa, editor, 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  34. Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets. In Andréa W. Richa, editor, 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  35. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. Fast Distributed Algorithms for Connectivity and MST in Large Graphs. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 429-438, 2016. URL: https://doi.org/10.1145/2935764.2935785.
  36. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the Distributed Complexity of Large-Scale Graph Computations. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018, pages 405-414, 2018. URL: https://doi.org/10.1145/3210377.3210409.
  37. David Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, 2000. Google Scholar
  38. Andrew Chi-Chih Yao. Some Complexity Questions Related to Distributive Computing(Preliminary Report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 209-213, New York, NY, USA, 1979. ACM. URL: https://doi.org/10.1145/800135.804414.
  39. Grigory Yaroslavtsev and Adithya Vadapalli. Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under 𝓁_p Distances. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 5596-5605, 2018. URL: http://proceedings.mlr.press/v80/yaroslavtsev18a.html.
  40. J. Yu, L. Jia, D. Yu, G. Li, and X. Cheng. Minimum connected dominating set construction in wireless networks under the beeping model. In 2015 IEEE Conference on Computer Communications (INFOCOM), pages 972-980, April 2015. URL: https://doi.org/10.1109/INFOCOM.2015.7218469.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact