Document Open Access Logo

Connectivity Lower Bounds in Broadcast Congested Clique

Authors Shreyas Pai , Sriram V. Pemmaraju

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.32.pdf
  • Filesize: 0.62 MB
  • 17 pages

Document Identifiers

Author Details

Shreyas Pai
  • The University of Iowa, Iowa City, IA, USA
Sriram V. Pemmaraju
  • The University of Iowa, Iowa City, IA, USA

Cite AsGet BibTex

Shreyas Pai and Sriram V. Pemmaraju. Connectivity Lower Bounds in Broadcast Congested Clique. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.32

Abstract

We prove three new lower bounds for graph connectivity in the 1-bit broadcast congested clique model, BCC(1). First, in the KT-0 version of BCC(1), in which nodes are aware of neighbors only through port numbers, we show an Ω(log n) round lower bound for Connectivity even for constant-error randomized Monte Carlo algorithms. The deterministic version of this result can be obtained via the well-known "edge-crossing" argument, but, the randomized version of this result requires establishing new combinatorial results regarding the indistinguishability graph induced by inputs. In our second result, we show that the Ω(log n) lower bound result extends to the KT-1 version of the BCC(1) model, in which nodes are aware of IDs of all neighbors, though our proof works only for deterministic algorithms. This result substantially improves upon the existing Ω(log^* n) deterministic lower bound (Jurdziński et el., SIROCCO 2018) for this problem. Since nodes know IDs of their neighbors in the KT-1 model, it is no longer possible to play "edge-crossing" tricks; instead we present a reduction from the 2-party communication complexity problem Partition in which Alice and Bob are given two set partitions on [n] and are required to determine if the join of these two set partitions equals the trivial one-part set partition. While our KT-1 Connectivity lower bound holds only for deterministic algorithms, in our third result we extend this Ω(log n) KT-1 lower bound to constant-error Monte Carlo algorithms for the closely related ConnectedComponents problem. We use information-theoretic techniques to obtain this result. All our results hold for the seemingly easy special case of Connectivity in which an algorithm has to distinguish an instance with one cycle from an instance with multiple cycles. Our results showcase three rather different lower bound techniques and lay the groundwork for further improvements in lower bounds for Connectivity in the BCC(1) model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Communication complexity
  • Mathematics of computing → Information theory
Keywords
  • Distributed Algorithms
  • Broadcast Congested Clique
  • Connectivity
  • Lower Bounds
  • Indistinguishability
  • Communication Complexity
  • Information Theory

Metrics

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

Related Versions

  • A full version of this paper is available at: https://arxiv.org/abs/1905.09016. A short version of this paper has appeared as a brief announcement in PODC 2019.

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen. Fooling views: A new lower bound technique for distributed computations under congestion. CoRR, 2017. URL: http://arxiv.org/abs/1711.01623.
  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. URL: https://doi.org/10.1145/77600.77618.
  3. Mor Baruch, Pierre Fraigniaud, and Boaz Patt-Shamir. Randomized proof-labeling schemes. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 315-324, 2015. URL: https://doi.org/10.1145/2767386.2767421.
  4. Florent Becker, Antonio Fernández Anta, Ivan Rapaport, and Eric Rémila. The effect of range and bandwidth on the round complexity in the congested clique model. In Computing and Combinatorics - 22nd International Conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings, pages 182-193, 2016. URL: https://doi.org/10.1007/978-3-319-42634-1_15.
  5. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the CONGEST model. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 10:1-10:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.10.
  6. Moses Charikar, Weiyun Ma, and Li-Yang Tan. Unconditional lower bounds for adaptive massively parallel computation. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’20, page 141–151, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3350755.3400230.
  7. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, New York, NY, USA, 2006. Google Scholar
  8. Artur Czumaj and Christian Konrad. Detecting cliques in congest networks. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, July 2018. URL: http://wrap.warwick.ac.uk/106950/.
  9. 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. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 363-372, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993686.
  10. Thomas A. Dowling and Richard M. Wilson. Whitney number inequalities for geometric lattices. Proceedings of the American Mathematical Society, 47(2):504-504, 1975. URL: https://doi.org/10.1090/s0002-9939-1975-0354422-3.
  11. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 367-376, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2611462.2611493.
  12. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA '18, pages 153-162, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3210377.3210401.
  13. Mohsen Ghaffari and Merav Parter. MST in Log-Star Rounds of Congested Clique. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 19-28, 2016. URL: https://doi.org/10.1145/2933057.2933103.
  14. András Hajnal, Wolfgang Maass, and György Turán. On the communication complexity of graph properties. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 186-191, 1988. URL: https://doi.org/10.1145/62212.62228.
  15. 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, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2767386.2767434.
  16. Stephan Holzer and Nathan Pinsker. Approximation of distances and shortest paths in the broadcast congest clique. In 19th International Conference on Principles of Distributed Systems, OPODIS 2015, December 14-17, 2015, Rennes, France, pages 6:1-6:16, 2015. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2015.6.
  17. Joseph Já Já. The vlsi complexity of selected graph problems. J. ACM, 31(2):377-391, March 1984. URL: https://doi.org/10.1145/62.70.
  18. Tomasz Jurdzinski, Krzysztof Lorys, and Krzysztof Nowicki. Communication complexity in vertex partition whiteboard model. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, pages 264-279, 2018. URL: https://doi.org/10.1007/978-3-030-01325-7_24.
  19. Tomasz Jurdzinski and Krzysztof Nowicki. Brief announcement: On connectivity in the broadcast congested clique. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 54:1-54:4, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.54.
  20. 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.
  21. E. Korach, S. Moran, and S. Zaks. The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM J. Comput., 16(2):231-236, April 1987. URL: https://doi.org/10.1137/0216019.
  22. Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215-233, 2010. URL: https://doi.org/10.1007/s00446-010-0095-3.
  23. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  24. Pedro Montealegre and Ioan Todinca. Brief announcement: Deterministic graph connectivity in the broadcast congested clique. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 245-247, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2933057.2933066.
  25. Pedro Montealegre and Ioan Todinca. Deterministic graph connectivity in the broadcast congested clique. CoRR, abs/1602.04095, 2016. URL: http://arxiv.org/abs/1602.04095.
  26. Jelani Nelson and Huacheng Yu. Optimal lower bounds for distributed and streaming spanning forest computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, page 1844–1860, USA, 2019. Society for Industrial and Applied Mathematics. Google Scholar
  27. Boaz Patt-Shamir and Mor Perry. Proof-labeling schemes: Broadcast, unicast and in between. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium, SSS 2017, Boston, MA, USA, November 5-8, 2017, Proceedings, pages 1-17, 2017. URL: https://doi.org/10.1007/978-3-319-69084-1_1.
  28. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  29. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and circuits: (on lower bounds for modern parallel computation). 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 1-12, 2016. URL: https://doi.org/10.1145/2935764.2935799.
  30. D.J.A. Welsh. Matroid theory. Dover Publications, 2010. URL: http://www.worldcat.org/oclc/319491697?referer=xid.
  31. A. C. Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227, October 1977. URL: https://doi.org/10.1109/SFCS.1977.24.
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