Document Open Access Logo

(Delta+1) Coloring in the Congested Clique Model

Author Merav Parter

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.160.pdf
  • Filesize: 0.86 MB
  • 14 pages

Document Identifiers

Author Details

Merav Parter
  • Weizmann IS, Rehovot, Israel

Cite AsGet BibTex

Merav Parter. (Delta+1) Coloring in the Congested Clique Model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 160:1-160:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.160

Abstract

In this paper, we present improved algorithms for the (Delta+1) (vertex) coloring problem in the Congested Clique model of distributed computing. In this model, the input is a graph on n nodes, initially each node knows only its incident edges, and per round each two nodes can exchange O(log n) bits of information. Our key result is a randomized (Delta+1) vertex coloring algorithm that works in O(log log Delta * log^* Delta)-rounds. This is achieved by combining the recent breakthrough result of [Chang-Li-Pettie, STOC'18] in the {LOCAL} model and a degree reduction technique. We also get the following results with high probability: (1) (Delta+1)-coloring for Delta=O((n/log n)^{1-epsilon}) for any epsilon in (0,1), within O(log(1/epsilon)log^* Delta) rounds, and (2) (Delta+Delta^{1/2+o(1)})-coloring within O(log^* Delta) rounds. Turning to deterministic algorithms, we show a (Delta+1)-coloring algorithm that works in O(log Delta) rounds. Our new bounds provide exponential improvements over the state of the art.

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
    0
    Metadata Views

Related Versions

References

  1. Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. CoRR, abs/1711.01871, 2017. URL: http://arxiv.org/abs/1711.01871.
  2. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM (JACM), 63(3):20, 2016. Google Scholar
  3. József Beck. An algorithmic approach to the lovász local lemma. i. Random Structures &Algorithms, 2(4):343-365, 1991. Google Scholar
  4. 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
  5. 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
  6. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 615-624, 2016. Google Scholar
  7. Yi-Jun Chang, Wenzheng Li, and Seth Pettie. An optimal distributed (Δ+1) coloring algorithm? arXiv preprint arXiv:1711.01361, 2018. Google Scholar
  8. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the local model. FOCS, 2017. Google Scholar
  9. Manuela Fischer and Mohsen Ghaffari. Sublogarithmic distributed algorithms for Lov$$1'asz local lemma, and the complexity hierarchy. DISC, 2017. Google Scholar
  10. Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 625-634. IEEE, 2016. Google Scholar
  11. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 270-277. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  12. 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
  13. 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
  14. James W Hegeman and Sriram V Pemmaraju. Lessons from the congested clique applied to mapreduce. Theoretical Computer Science, 608:268-281, 2015. Google Scholar
  15. 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
  16. Janne H Korhonen and Jukka Suomela. Brief announcement: Towards a complexity theory for the congested clique. In LIPIcs-Leibniz International Proceedings in Informatics, volume 91. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  17. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM (JACM), 63(2):17, 2016. Google Scholar
  18. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In PODC, pages 42-50, 2013. Google Scholar
  19. 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
  20. Y Maus, F Kuhn, and M Ghaffari. On the complexity of local distributed graph problems. In Proceedings of the Annual ACM Symposium on Theory of Computing, pages 784-797, 2017. Google Scholar
  21. Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. Google Scholar
  22. Merav Parter. (δ+1) coloring in the congested clique model. arXiv, 2018. URL: http://arxiv.org/abs/1805.02457.
  23. 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
  24. Gregory Schwartzman. Adapting sequential algorithms to the distributed setting. arXiv preprint arXiv:1711.10155, 2017. Google Scholar
  25. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. URL: http://dx.doi.org/10.1561/0400000010.
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