Document Open Access Logo

Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model

Authors Ioannis Anagnostides, Themis Gouleakis

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.5.pdf
  • Filesize: 0.82 MB
  • 19 pages

Document Identifiers

Author Details

Ioannis Anagnostides
  • Department of Computer Engineering, National Technical University of Athens, Greece
Themis Gouleakis
  • Max Planck Institute for Informatics, Saarbrücken, Germany

Acknowledgements

We are indebted to Christoph Lenzen for carefully reviewing an earlier draft of our work, and proposing several improvements and interesting directions. Specifically, he suggested derandomizing Proposition 7 via the Garay-Kutten-Peleg algorithm, while he also pointed out the connection with low-congestion shortcuts, leading to the results of Section 4. We are also very grateful to the anonymous reviewers at DISC for carefully reviewing this paper, and for indicating many corrections and ways to improve the exposition. We are particularly thankful to a reviewer for providing very detailed arguments which strengthened our results in Section 3.4. All errors remain our own.

Cite As Get BibTex

Ioannis Anagnostides and Themis Gouleakis. Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.5

Abstract

The HYBRID model was recently introduced by Augustine et al. [John Augustine et al., 2020] in order to characterize from an algorithmic standpoint the capabilities of networks which combine multiple communication modes. Concretely, it is assumed that the standard LOCAL model of distributed computing is enhanced with the feature of all-to-all communication, but with very limited bandwidth, captured by the node-capacitated clique (NCC). In this work we provide several new insights on the power of hybrid networks for fundamental problems in distributed algorithms.
First, we present a deterministic algorithm which solves any problem on a sparse n-node graph in 𝒪̃(√n) rounds of HYBRID, where the notation 𝒪̃(⋅) suppresses polylogarithmic factors of n. We combine this primitive with several sparsification techniques to obtain efficient distributed algorithms for general graphs. Most notably, for the all-pairs shortest paths problem we give deterministic (1 + ε)- and log n/log log n-approximate algorithms for unweighted and weighted graphs respectively with round complexity 𝒪̃(√n) in HYBRID, closely matching the performance of the state of the art randomized algorithm of Kuhn and Schneider [Kuhn and Schneider, 2020]. Moreover, we make a connection with the Ghaffari-Haeupler framework of low-congestion shortcuts [Mohsen Ghaffari and Bernhard Haeupler, 2016], leading - among others - to a (1 + ε)-approximate algorithm for Min-Cut after 𝒪(polylog (n)) rounds, with high probability, even if we restrict local edges to transfer 𝒪(log n) bits per round. Finally, we prove via a reduction from the set disjointness problem that Ω̃(n^{1/3}) rounds are required to determine the radius of an unweighted graph, as well as a (3/2 - ε)-approximation for weighted graphs. As a byproduct, we show an Ω̃(n) round-complexity lower bound for computing a (4/3 - ε)-approximation of the radius in the broadcast variant of the congested clique, even for unweighted graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Computing
  • Hybrid Model
  • Sparse Graphs
  • Deterministic Algorithms
  • All-Pairs Shortest Paths
  • Minimum Cut
  • Radius

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, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing - 30th International Symposium, DISC 2016, volume 9888 of Lecture Notes in Computer Science, pages 29-42. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_3.
  2. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pages 1681-1697. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.112.
  3. Ioannis Anagnostides and Themis Gouleakis. Deterministic distributed algorithms and lower bounds in the hybrid model, 2021. URL: http://arxiv.org/abs/2108.01740.
  4. Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1-5:37, 2009. URL: https://doi.org/10.1145/1502793.1502794.
  5. John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Fabian Kuhn, and Jason Li. Distributed computation in node-capacitated networks. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, pages 69-79. ACM, 2019. URL: https://doi.org/10.1145/3323165.3323195.
  6. John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, and Philipp Schneider. Shortest paths in a hybrid network model. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1280-1299. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.78.
  7. Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng. Spectral sparsification of graphs: theory and algorithms. Commun. ACM, 56(8):87-94, 2013. URL: https://doi.org/10.1145/2492007.2492029.
  8. András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n^2) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996, pages 47-55. ACM, 1996. URL: https://doi.org/10.1145/237814.237827.
  9. Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. Distance computations in the hybrid network model via oracle simulations, 2020. URL: http://arxiv.org/abs/2010.13831.
  10. Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. On sparsity awareness in distributed computations. In Kunal Agrawal and Yossi Azar, editors, SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021, pages 151-161. ACM, 2021. URL: https://doi.org/10.1145/3409964.3461798.
  11. Tao Chen, Xiaofeng Gao, and Guihai Chen. The features, hardware, and architectures of data center networks: A survey. Journal of Parallel and Distributed Computing, 96:45-74, 2016. URL: https://doi.org/10.1016/j.jpdc.2016.05.009.
  12. Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, page 273–282, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1993636.1993674.
  13. 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, page 363–372. Association for Computing Machinery, 2011. URL: https://doi.org/10.1145/1993636.1993686.
  14. Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Distributed weighted min-cut in nearly-optimal time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pages 1144-1153. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451020.
  15. 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, pages 367-376. ACM, 2014. URL: https://doi.org/10.1145/2611462.2611493.
  16. Michael Elkin and Shaked Matar. Ultra-sparse near-additive emulators. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC '21: ACM Symposium on Principles of Distributed Computing, 2021, pages 235-246. ACM, 2021. URL: https://doi.org/10.1145/3465084.3467926.
  17. Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Helios: A hybrid electrical/optical switch architecture for modular data centers. In Proceedings of the ACM SIGCOMM 2010 Conference, SIGCOMM '10, page 339–350, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1851182.1851223.
  18. Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler. Fast hybrid network algorithms for shortest paths in sparse graphs, 2020. URL: http://arxiv.org/abs/2007.01191.
  19. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, page 1150–1162. Society for Industrial and Applied Mathematics, 2012. URL: https://doi.org/10.1137/1.9781611973099.91.
  20. Juan A. Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput., 27(1):302-316, 1998. URL: https://doi.org/10.1137/S0097539794261118.
  21. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks II: low-congestion shortcuts, mst, and min-cut. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 202-219. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch16.
  22. Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. In Yehuda Afek, editor, Distributed Computing, pages 1-15, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-41527-2_1.
  23. Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing, DISC 2018, volume 121 of LIPIcs, pages 29:1-29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.29.
  24. Mohsen Ghaffari and Krzysztof Nowicki. Congested clique algorithms for the minimum cut problem. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, page 357–366, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://dl.acm.org/citation.cfm?id=3212750.
  25. Thorsten Götte, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. Time-optimal construction of overlay networks, 2020. URL: http://arxiv.org/abs/2009.03987.
  26. Bernhard Haeupler and Jason Li. Faster distributed shortest path approximations via shortcuts. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing, DISC 2018, volume 121 of LIPIcs, pages 33:1-33:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.33.
  27. Johan Håstad and Avi Wigderson. The randomized communication complexity of set disjointness. Theory Comput., 3(1):211-219, 2007. URL: https://doi.org/10.4086/toc.2007.v003a011.
  28. Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discret. Math., 5(4):545-557, 1992. URL: https://doi.org/10.1137/0405044.
  29. Udit Narayana Kar and Debarshi Kumar Sanyal. An overview of device-to-device communication in cellular networks. ICT Express, 4(4):203-208, 2018. URL: https://doi.org/10.1016/j.icte.2017.08.002.
  30. David R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '93, page 21–30, USA, 1993. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=313559.313605.
  31. P. Klein, C. Stein, and É. Tardos. Leighton-rao might be practical: Faster approximation algorithms for concurrent flow with uniform capacities. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC '90, page 310–321. Association for Computing Machinery, 1990. URL: https://doi.org/10.1145/100216.100257.
  32. Ioannis Koutis. Simple parallel and distributed algorithms for spectral graph sparsification, 2014. URL: http://arxiv.org/abs/1402.3851.
  33. Fabian Kuhn and Philipp Schneider. Computing shortest paths and diameter in the hybrid network model. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC '20, page 109–118. Association for Computing Machinery, 2020. URL: https://doi.org/10.1145/3382734.3405719.
  34. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013, pages 42-50. ACM, 2013. URL: https://doi.org/10.1145/2484239.2501983.
  35. Christoph Lenzen. Lectures notes on Theory of Distributed Systems. , 2016. URL: https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/winter15/tods/ToDS.pdf.
  36. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014.
  37. P. Li, S. Guo, and I. Stojmenovic. A truthful double auction for device-to-device communications in cellular networks. IEEE Journal on Selected Areas in Communications, 34(1):71-81, 2016. URL: https://doi.org/10.1109/JSAC.2015.2452587.
  38. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–201, 1992. URL: https://doi.org/10.1137/0221015.
  39. Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. MST construction in O(log log n) communication rounds. In Arnold L. Rosenberg and Friedhelm Meyer auf der Heide, editors, SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 94-100. ACM, 2003. URL: https://doi.org/10.1145/777412.777428.
  40. Robert Meusel, Sebastiano Vigna, Oliver Lehmberg, and Christian Bizer. The graph structure in the web – analyzed on different aggregation levels. The Journal of Web Science, 1(1):33-47, 2015. URL: https://doi.org/10.1561/106.00000003.
  41. A. Murkaz, R. Hussain, S. F. Hasan, M. Y. Chung, B. . Seet, P. H. J. Chong, S. T. Shah, and S. A. Malik. Architecture and protocols for inter-cell device-to-device communication in 5G networks. In 2016 IEEE 14th Intl Conf on Dependable, Autonomic and Secure Computing, 14th Intl Conf on Pervasive Intelligence and Computing, 2nd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress(DASC/PiCom/DataCom/CyberSciTech), pages 489-492, 2016. URL: https://doi.org/10.1109/DASC-PICom-DataCom-CyberSciTec.2016.95.
  42. Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In Fabian Kuhn, editor, Distributed Computing, pages 439-453, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-662-45174-8_30.
  43. Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, 129:192-224, 2006. URL: https://doi.org/10.1016/j.jet.2004.10.007.
  44. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA, 2000. Google Scholar
  45. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed mst construction. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS '99, page 253, USA, 1999. IEEE Computer Society. URL: https://doi.org/10.1109/SFFCS.1999.814597.
  46. David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM J. Comput., 18(4):740-747, 1989. URL: https://doi.org/10.1137/0218050.
  47. Ran Raz and Avi Wigderson. Monotone circuits for matching require linear depth. J. ACM, 39(3):736–744, 1992. URL: https://doi.org/10.1145/146637.146684.
  48. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, pages 515-524. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488673.
  49. Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 350-363. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384298.
  50. C. Wang, F. Haider, X. Gao, X. You, Y. Yang, D. Yuan, H. M. Aggoune, H. Haas, S. Fletcher, and E. Hepsaydir. Cellular architecture and key technologies for 5G wireless communication networks. IEEE Communications Magazine, 52(2):122-130, 2014. URL: https://doi.org/10.1109/MCOM.2014.6736752.
  51. Guohui Wang, David G. Andersen, Michael Kaminsky, Konstantina Papagiannaki, T.S. Eugene Ng, Michael Kozuch, and Michael Ryan. C-through: Part-time optics in data centers. SIGCOMM Comput. Commun. Rev., 40(4):327–338, August 2010. URL: https://doi.org/10.1145/1851182.1851222.
  52. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing(preliminary report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, page 209–213, New York, NY, USA, 1979. Association for Computing Machinery. URL: https://doi.org/10.1145/800135.804414.
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