Document Open Access Logo

Computing Power of Hybrid Models in Synchronous Networks

Authors Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, Ioan Todinca

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.20.pdf
  • Filesize: 0.81 MB
  • 18 pages

Document Identifiers

Author Details

Pierre Fraigniaud
  • IRIF, Université Paris Cité and CNRS, France
Pedro Montealegre
  • Faculty of Engineering and Science, Adolfo Ibáñez University, Santiago, Chile
Pablo Paredes
  • Department of Mathematical Engineering, University of Chile, Santiago, Chile
Ivan Rapaport
  • DIM-CMM (UMI 2807 CNRS), University of Chile, Santiago, Chile
Martín Ríos-Wilson
  • Faculty of Engineering and Science, Adolfo Ibáñez University, Santiago, Chile
Ioan Todinca
  • LIFO, Université d'Orléans and INSA Centre-Val de Loire, France

Funding

  • Fraigniaud, Pierre: Additional support for ANR projects QuData and DUCAT.
  • Montealegre, Pedro: This work was supported by Centro de Modelamiento Matemático (CMM), FB210005, BASAL funds for centers of excellence from ANID-Chile, and ANID-PAI77170068.
  • Rapaport, Ivan: This work was supported by Centro de Modelamiento Matemático (CMM), FB210005, BASAL funds for centers of excellence from ANID-Chile, and ANID-FONDECYT 1220142.
  • Ríos-Wilson, Martín: Additional support from ANID-FONDECYT Postdoctorado 3220205.

Cite As Get BibTex

Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca. Computing Power of Hybrid Models in Synchronous Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.OPODIS.2022.20

Abstract

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of an independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector x ∈ {0,1}ⁿ together with an index i ∈ [n], Bob is given a binary vector y ∈ {0,1}ⁿ together with an index j ∈ [n], and, after a single round of 2-way communication, Alice must output a boolean out_A, and Bob must output a boolean out_B, such that out_A ∧ out_B = x_j⊕ y_i. We show that the communication complexity of XOR-Index is Ω(n) bits.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • hybrid model
  • synchronous networks
  • LOCAL
  • CONGEST
  • Broadcast Congested Clique

Metrics

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

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. ACM Transactions on Algorithms (TALG), 17(4):1-40, 2021. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In 23rd ACM-SIAM symposium on Discrete Algorithms, pages 459-467, 2012. Google Scholar
  3. Ioannis Anagnostides and Themis Gouleakis. Deterministic distributed algorithms and lower bounds in the hybrid model. In 35th International Symposium on Distributed Computing (DISC), volume 209 of LIPIcs, pages 5:1-5:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  4. Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? SIGACT News, 45(3):82-104, 2014. Google Scholar
  5. Czumaj Artur and Christian Konrad. Detecting cliques in congest networks. Distributed Computing, 33(6):533-543, 2020. Google Scholar
  6. John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Fabian Kuhn, and Jason Li. Distributed computation in node-capacitated networks. In 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 69-79, 2019. Google Scholar
  7. John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, and Philipp Schneider. Shortest paths in a hybrid network model. In 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1280-1299, 2020. Google Scholar
  8. László Babai, Anna Gál, Peter G Kimmel, and Satyanarayana V Lokam. Communication complexity of simultaneous messages. SIAM Journal on Computing, 33(1):137-166, 2003. Google Scholar
  9. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. In 40th ACM Symposium on Principles of Distributed Computing (PODC), pages 263-272, 2021. Google Scholar
  10. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2+ ε)-approximation for vertex cover in O(log Δ / ε log log Δ) rounds. Journal of the ACM, 64(3):1-11, 2017. Google Scholar
  11. Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. Theoretical Computer Science, 751:2-23, 2018. Google Scholar
  12. Florent Becker, Adrian Kosowski, Martín Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, and Ioan Todinca. Allowing each node to communicate only once in a distributed system: shared whiteboard models. Distributed Comput., 28(3):189-200, 2015. Google Scholar
  13. Florent Becker, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, and Ioan Todinca. Adding a referee to an interconnection network: What can (not) be computed in one round. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 508-514, 2011. Google Scholar
  14. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. Distributed Comput., 32(1):41-57, 2019. Google Scholar
  15. Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. Distance computations in the hybrid network model via oracle simulations. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 187 of LIPIcs, pages 21:1-21:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  16. Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. On sparsity awareness in distributed computations. In 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 151-161, 2021. Google Scholar
  17. Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of (Δ+ 1) coloring in congested clique, massively parallel computation, and centralized local computation. In ACM Symposium on Principles of Distributed Computing (PODC), pages 471-480, 2019. Google Scholar
  18. Lijie Chen and Ofer Grossman. Broadcast congested clique: Planted cliques and pseudorandom generators. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 248-255, 2019. Google Scholar
  19. John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880-884, 1969. Google Scholar
  20. Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs. Near-shortest path routing in hybrid communication networks. In 25th International Conference on Principles of Distributed Systems (OPODIS), volume 217 of LIPIcs, pages 11:1-11:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  21. 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, pages 367-376, 2014. Google Scholar
  22. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 367-376. ACM, 2014. URL: https://doi.org/10.1145/2611462.2611493.
  23. Albert Einstein, Boris Podolsky, and Nathan Rosen. Can quantum-mechanical description of physical reality be considered complete? Physical Review, 47(10):777-780, 1935. Google Scholar
  24. Michael Elkin. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM Journal on Computing, 36(2):433-456, 2006. Google Scholar
  25. Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three notes on distributed property testing. In 31st International Symposium on Distributed Computing (DISC), volume 91 of LIPIcs, pages 15:1-15:30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  26. Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler. Fast hybrid network algorithms for shortest paths in sparse graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS), volume 184 of LIPIcs, pages 31:1-31:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  27. Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bull. EATCS, 119, 2016. Google Scholar
  28. Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. J. ACM, 60(5):35:1-35:26, 2013. Google Scholar
  29. Pierre Fraigniaud and Dennis Olivetti. Distributed detection of cycles. ACM Trans. Parallel Comput., 6(3):12:1-12:20, 2019. Google Scholar
  30. Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed testing of excluded subgraphs. In 30th International Symposium on Distributed Computing (DISC), volume 9888 of LNCS, pages 342-356. Springer, 2016. Google Scholar
  31. Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory Comput., 12(1):1-33, 2016. Google Scholar
  32. Thorsten Götte, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. Time-optimal construction of overlay networks. In 40th ACM Symposium on Principles of Distributed Computing (PODC), pages 457-468. ACM, 2021. Google Scholar
  33. 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), 2016. Google Scholar
  34. Tomasz Jurdziński and Krzysztof Nowicki. Connectivity and minimum cut approximation in the broadcast congested clique. In International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 331-344. Springer, 2018. Google Scholar
  35. Tomasz Jurdziński and Krzysztof Nowicki. Mst in O(1) rounds of congested clique. In 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2620-2632, 2018. Google Scholar
  36. Gillat Kol, Rotem Oshman, and Raghuvansh R. Saxena. Interactive distributed proofs. In 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 255-264, 2018. Google Scholar
  37. Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Comput., 22(4):215-233, 2010. Google Scholar
  38. Fabian Kuhn, Thomas Moscibroda, and Rogert Wattenhofer. What cannot be computed locally! In 23rd ACM Symposium on Principles of Distributed Computing (PODC), pages 300-309, 2004. Google Scholar
  39. Fabian Kuhn and Philipp Schneider. Computing shortest paths and diameter in the hybrid network model. In 39th ACM Symposium on Principles of Distributed Computing (PODC), pages 109-118, 2020. Google Scholar
  40. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In ACM Symposium on Principles of Distributed Computing (PODC), pages 42-50, 2013. Google Scholar
  41. Reut Levi, Moti Medina, and Dana Ron. Property testing of planarity in the CONGEST model. Distributed Comput., 34(1):15-32, 2021. Google Scholar
  42. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. Google Scholar
  43. Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. Mst construction in o (log log n) communication rounds. In 15th ACM sSmposium on Parallel Algorithms and Architectures (SPAA), pages 94-100, 2003. Google Scholar
  44. Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1096-115, 2020. Google Scholar
  45. Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. Google Scholar
  46. Noam Nisan and Avi Widgerson. Rounds in communication complexity revisited. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 419-429, 1991. Google Scholar
  47. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  48. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM Journal on Computing, 30(5):1427-1442, 2000. Google Scholar
  49. Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. Google Scholar
  50. 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. SIAM Journal on Computing, 41(5):1235-1265, 2012. Google Scholar
  51. Rangarajan K Sundaram et al. A first course in optimization theory. Cambridge university press, 1996. Google Scholar
  52. Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24:1-24:40, 2013. Google Scholar
  53. Jukka Suomela. Landscape of locality. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 162 of LIPIcs, pages 2:1-2:1, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  54. Huacheng Yu. Tight distributed sketching lower bound for connectivity. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1856-1873, 2021. 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