Document Open Access Logo

Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets

Authors Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.38.pdf
  • Filesize: 0.64 MB
  • 16 pages

Document Identifiers

Author Details

Shreyas Pai
Gopal Pandurangan
Sriram V. Pemmaraju
Talal Riaz
Peter Robinson

Cite As Get BibTex

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 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.38

Abstract

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time (round) complexity of MIS (and ruling sets) have attracted much attention in the Local model. Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem have tried to break the long-standing O(log n)-round "barrier" achieved by Luby's algorithm, but these yield o(log n)-round complexity only when the maximum degree Delta is somewhat small relative to n. More importantly, these results apply only in the Local model. In fact, the best known time bound in the Congest model is still O(log n) (via Luby's algorithm) even for moderately small Delta (i.e., for Delta = Omega(log n) and Delta = o(n)). Furthermore, message complexity has been largely ignored in the context of local symmetry breaking. Luby's algorithm takes O(m) messages on m-edge graphs and this is the best known bound with respect to messages. Our work is motivated by the following central question: can we break the Theta(log n) time complexity barrier and the Theta(m) message complexity barrier in the Congest model for MIS or closely-related symmetry breaking problems?

This paper presents progress towards this question for the distributed ruling set problem in the Congest model. A beta-ruling set is an independent set such that every node in the graph is at most beta hops from a node in the independent set. We present the following results:

- Time Complexity: We show that we can break the O(log n) "barrier" for 2- and 3-ruling sets. We compute 3-ruling sets in O(log n/log log n) rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in O(log Delta (log n)^(1/2 + epsilon) + log n/log log n) rounds for any epsilon > 0, which is o(log n) for a wide range of Delta values (e.g., Delta = 2^(log n)^(1/2-epsilon)). These are the first 2- and 3-ruling set algorithms to improve over the O(log n)-round complexity of Luby's algorithm in the Congest model.

- Message Complexity: We show an Omega(n^2) lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only O(n log^2 n) messages and runs in O(Delta log n) rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in n (which is optimal up to a polylogarithmic factor).

Subject Classification

Keywords
  • Congest model
  • Local model
  • Maximal independent set
  • Message complexity
  • Round complexity
  • Ruling sets
  • Symmetry breaking

Metrics

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

References

  1. 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
  2. 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. Google Scholar
  3. Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (δ+1)-coloring in linear (in δ) time. SIAM Journal on Computing, 43(1):72-95, 2014. Google Scholar
  4. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 321-330, 2012. Google Scholar
  5. 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. Google Scholar
  6. József Beck. An algorithmic approach to the Lovász Local Lemma. I. Random Struct. Algorithms, 2(4):343-365, December 1991. Google Scholar
  7. Tushar Bisht, Kishore Kothapalli, and Sriram Pemmaraju. Brief announcement: Super-fast t-ruling sets. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC'14, pages 379-381, New York, NY, USA, 2014. ACM. Google Scholar
  8. T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. The MIT Press, 1990. Google Scholar
  9. Devdatt Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2009. Google Scholar
  10. 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. Google Scholar
  11. A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry breaking in sparse graphs. SIAM J. Discrete Math., 1:434-446, 1989. Google Scholar
  12. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 489-498, 2016. Google Scholar
  13. 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
  14. Kishore Kothapalli and Sriram V. Pemmaraju. Super-fast 3-ruling sets. In FSTTCS, pages 136-147, 2012. Google Scholar
  15. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17:1-17:44, March 2016. Google Scholar
  16. 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, 2015. URL: http://dx.doi.org/10.1145/2699440.
  17. M. Luby. A simple parallel algorithm for the maximal independent set. SIAM Journal on Computing, 15:1036-1053, 1986. Google Scholar
  18. 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. ArXiv e-prints, May 2017. URL: https://arxiv.org/abs/1705.07861.
  19. A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition. J. Algorithms, 20(2):356-374, 1996. Google Scholar
  20. David Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, 2000. 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