Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds

Authors Merav Parter, Hsin-Hao Su



PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.39.pdf
  • Filesize: 0.94 MB
  • 18 pages

Document Identifiers

Author Details

Merav Parter
  • Weizmann IS, Rehovot, Israel
Hsin-Hao Su
  • UNC-Charlotte, North Carolina, USA

Cite AsGet BibTex

Merav Parter and Hsin-Hao Su. Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.39

Abstract

(Delta+1)-vertex coloring is one of the most fundamental symmetry breaking graph problems, receiving tremendous amount of attention over the last decades. We consider the congested clique model where in each round, every pair of vertices can exchange O(log n) bits of information. In a recent breakthrough, Yi-Jun Chang, Wenzheng Li, and Seth Pettie [CLP-STOC'18] presented a randomized (Delta+1)-list coloring algorithm in the LOCAL model that works in O(log^*n+Det_{deg}(log log n)) rounds, where Det_{deg}(n') is the deterministic LOCAL complexity of (deg+1)-list coloring algorithm on n'-vertex graphs. Unfortunately, the CLP algorithm uses large messages and hence cannot be efficiently implemented in the congested clique model when the maximum degree Delta is large (in particular, when Delta=omega(sqrt{n})). Merav Parter [P-ICALP'18] recently provided a randomized (Delta+1)-coloring algorithm in O(log log Delta * log^* Delta) congested clique rounds based on a careful partitioning of the input graph into almost-independent subgraphs with maximum degree sqrt{n}. In this work, we significantly improve upon this result and present a randomized (Delta+1)-coloring algorithm with O(log^* Delta) rounds, with high probability. At the heart of our algorithm is an adaptation of the CLP algorithm for coloring a subgraph with o(n) vertices and maximum degree Omega(n^{5/8}) in O(log^* Delta) rounds. The approach is built upon a combination of techniques, this includes: the graph sparsification of [Parter-ICALP'18], and a palette sampling technique adopted to the CLP framework.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Graph Algorithms
  • Coloring
  • congested clique

Metrics

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

References

  1. Leonid Barenboim and Victor Khazanov. Distributed symmetry-breaking algorithms for congested cliques. arXiv preprint arXiv:1802.07209, 2018. Google Scholar
  2. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Brief announcement: Semi-mapreduce meets congested clique. arXiv preprint arXiv:1802.10297, 2018. Google Scholar
  3. Andrew Berns, James Hegeman, and Sriram V Pemmaraju. Super-fast distributed algorithms for metric facility location. In International Colloquium on Automata, Languages, and Programming, pages 428-439. Springer, 2012. Google Scholar
  4. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 11:1-11:16, 2017. Google Scholar
  5. Yi-Jun Chang, Wenzheng Li, and Seth Pettie. An optimal distributed (Δ+1)-coloring algorithm? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, pages 445-456. ACM, 2018. Google Scholar
  6. Mohsen Ghaffari. Distributed MIS via all-to-all communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 141-149, 2017. Google Scholar
  7. 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, pages 129-138, 2018. Google Scholar
  8. David G Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (Δ+ 1)-coloring in sublogarithmic rounds. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 465-478. ACM, 2016. Google Scholar
  9. James W Hegeman and Sriram V Pemmaraju. Lessons from the congested clique applied to mapreduce. Theoretical Computer Science, 608:268-281, 2015. Google Scholar
  10. James W Hegeman, Sriram V Pemmaraju, and Vivek B Sardeshmukh. Near-constant-time distributed algorithms on a congested clique. In International Symposium on Distributed Computing, pages 514-530. Springer, 2014. Google Scholar
  11. Tomasz Jurdzinski 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 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2620-2632, 2018. Google Scholar
  12. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM (JACM), 63(2):17, 2016. Google Scholar
  13. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 42-50. ACM, 2013. Google Scholar
  14. 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
  15. Merav Parter. (Δ+1) coloring in the congested clique model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 160:1-160:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  16. Merav Parter. (Δ+1) coloring in the congested clique model. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.02457.
  17. Johannes Schneider and Roger Wattenhofer. A new technique for distributed symmetry breaking. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 257-266. ACM, 2010. 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