Document Open Access Logo

Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts

Authors Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, Themis Gouleakis

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.6.pdf
  • Filesize: 0.87 MB
  • 20 pages

Document Identifiers

Author Details

Ioannis Anagnostides
  • Carnegie Mellon University, Pittsburgh, PA, USA
Christoph Lenzen
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Bernhard Haeupler
  • ETH Zürich, Switzerland
Goran Zuzic
  • ETH Zürich, Switzerland
Themis Gouleakis
  • National University of Singapore, Singapore

Funding

  • Haeupler, Bernhard: Supported in part by NSF grants CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808, a Sloan Research Fellowship, funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (ERC grant agreement 949272), and the Swiss National Foundation (project grant 200021-184735).
  • Zuzic, Goran: Supported in part by the Swiss National Foundation (project grant 200021-184735).
  • Gouleakis, Themis: Supported in part by an NRF Fellowship for AI (R-252-000-A33-133). Part of the work was done while visiting the Simons Institute for Theory of Computing).

Acknowledgements

We are grateful to the anonymous reviewers for their valuable feedback.

Cite AsGet BibTex

Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis. Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.6

Abstract

In this paper, we refine the (almost) existentially optimal distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after n^{o(1)} SQ(G) log(1/ε) rounds, where ε is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires Ω̃(SQ(G)) rounds, even for a crude solution with ε ≤ 1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D ⋅ n^{o(1)} log(1/ε) rounds, where D is the hop-diameter of the network; as well as n^{o(1)} log (1/ε)-round algorithms for the case of SQ(G) ≤ n^{o(1)}, which holds for most networks of interest. Conditioned on improvements in state-of-the-art constructions of low-congestion shortcuts, the CONGEST results will match the Supported-CONGEST ones. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity n^{o(1)} log(1/ε). The unifying thread of these results, and our main technical contribution, is the study of a novel ρ-congested generalization of the standard part-wise aggregation problem. We develop near-optimal algorithms for this primitive in the Supported-CONGEST model, almost-optimal algorithms in (standard) CONGEST (with the additional overhead due to standard barriers), as well as a simple algorithm for bounded-treewidth graphs with a quadratic dependence on the congestion ρ. This primitive can be readily used to accelerate the Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye, and we believe it will find further independent applications in the future.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed algorithms
  • Laplacian solvers
  • low-congestion shortcuts

Metrics

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

Related Versions

References

  1. Ioannis Anagnostides and Themis Gouleakis. Deterministic distributed algorithms and lower bounds in the hybrid model. In 35th International Symposium on Distributed Computing, DISC 2021, volume 209 of LIPIcs, pages 5:1-5:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.5.
  2. 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.
  3. 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, pages 1280-1299. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.78.
  4. Kyriakos Axiotis, Aleksander Madry, and Adrian Vladu. Circulation control for faster minimum cost flow in unit-capacity graphs. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 93-104. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00018.
  5. Kyriakos Axiotis, Aleksander Madry, and Adrian Vladu. Faster sparse minimum cost flow by electrical flow localization. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 528-539. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00059.
  6. Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat Tangwongsan. Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Theory Comput. Syst., 55(3):521-554, 2014. URL: https://doi.org/10.1007/s00224-013-9444-5.
  7. 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 2021, volume 187 of LIPIcs, pages 21:1-21:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.21.
  8. 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, pages 151-161. ACM, 2021. URL: https://doi.org/10.1145/3409964.3461798.
  9. 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.
  10. Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu. Negative-weight shortest paths and unit capacity minimum cost flow in o(m^10/7 log W) time (extended abstract). In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 752-771. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.48.
  11. 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, 2022. URL: http://arxiv.org/abs/2202.08008.
  12. Samuel I. Daitch and Daniel A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pages 451-460. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374441.
  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, pages 363-372, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1993636.1993686.
  14. 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. Google Scholar
  15. Michael Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC '04, pages 331-340, New York, NY, USA, 2004. Association for Computing Machinery. URL: https://doi.org/10.1145/1007352.1007407.
  16. 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 2020, volume 184 of LIPIcs, pages 31:1-31:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2020.31.
  17. Sebastian Forster and Tijn de Vos. The laplacian paradigm in the broadcast congested clique. In PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, 2022, pages 335-344. ACM, 2022. URL: https://doi.org/10.1145/3519270.3538436.
  18. Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. Minor sparsifiers and the distributed laplacian paradigm. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 989-999. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00099.
  19. Mohsen Ghaffari. Near-Optimal Scheduling of Distributed Algorithms, pages 3-12. Association for Computing Machinery, New York, NY, USA, 2015. URL: https://doi.org/10.1145/2767386.2767417.
  20. 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.
  21. Mohsen Ghaffari and Bernhard Haeupler. Low-congestion shortcuts for graphs excluding dense minors. In PODC '21: ACM Symposium on Principles of Distributed Computing, 2021, pages 213-221. ACM, 2021. URL: https://doi.org/10.1145/3465084.3467935.
  22. Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir. Near-optimal distributed maximum flow: Extended abstract. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pages 81-90. ACM, 2015. URL: https://doi.org/10.1145/2767386.2767440.
  23. Mohsen Ghaffari and Goran Zuzic. Universally-optimal distributed exact min-cut. In PODC '22: ACM Symposium on Principles of Distributed Computing, 2022, pages 281-291. ACM, 2022. URL: https://doi.org/10.1145/3519270.3538429.
  24. Thorsten Götte, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. Time-optimal construction of overlay networks. In PODC '21: ACM Symposium on Principles of Distributed Computing, pages 457-468. ACM, 2021. URL: https://doi.org/10.1145/3465084.3467932.
  25. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. In George Giakkoupis, editor, Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, pages 451-460. ACM, 2016. URL: https://doi.org/10.1145/2933057.2933112.
  26. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on bounded parameter graphs. In Distributed Computing - 30th International Symposium, DISC 2016, volume 9888 of Lecture Notes in Computer Science, pages 158-172. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_12.
  27. Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari. Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pages 1325-1338. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520026.
  28. Bernhard Haeupler, David Wajc, and Goran Zuzic. Network coding gaps for completion times of multiple unicasts. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 494-505. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00053.
  29. Bernhard Haeupler, David Wajc, and Goran Zuzic. Universally-optimal distributed algorithms for known topologies. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1166-1179. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451081.
  30. Öjvind Johansson. Simple distributed δ + 1-coloring of graphs. Information Processing Letters, 70(5):229-232, 1999. Google Scholar
  31. 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.
  32. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 217-226. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.16.
  33. Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, 2013, pages 911-920. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488724.
  34. Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. SIAM J. Comput., 43(1):337-354, 2014. URL: https://doi.org/10.1137/110845914.
  35. 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, pages 109-118. Association for Computing Machinery, 2020. Google Scholar
  36. Fabian Kuhn and Philipp Schneider. Routing schemes and distance oracles in the hybrid model, 2022. URL: http://arxiv.org/abs/2202.06624.
  37. Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians - fast, sparse, and simple. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 573-582. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.68.
  38. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. Google Scholar
  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, 2003, pages 94-100. ACM, 2003. URL: https://doi.org/10.1145/777412.777428.
  40. Aleksander Madry. Computing maximum flow with augmenting electrical flows. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 593-602. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.70.
  41. D. Peleg and V. Rubinovich. A near-tight lower bound on the time complexity of distributed mst construction. In 40th Annual Symposium on Foundations of Computer Science, pages 253-261, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814597.
  42. David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000. Google Scholar
  43. Richard Peng. Approximate undirected maximum flows in O(mpolylog(n)) time. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 1862-1867. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch130.
  44. Richard Peng and Daniel A. Spielman. An efficient parallel solver for SDD linear systems. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, pages 333-342. ACM, 2014. Google Scholar
  45. Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li. Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pages 478-487. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520074.
  46. Stefan Schmid and Jukka Suomela. Exploiting locality in distributed sdn control. HotSDN 2013 - Proceedings of the 2013 ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, pages 121-126, 2013. URL: https://doi.org/10.1145/2491185.2491198.
  47. Daniel A. Spielman and Shang-Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl., 35(3):835-885, 2014. URL: https://doi.org/10.1137/090771430.
  48. Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 919-930. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00090.
  49. 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. In Proceedings of the ACM SIGCOMM 2010 Conference, SIGCOMM '10, pages 327-338. Association for Computing Machinery, 2010. URL: https://doi.org/10.1145/1851182.1851222.
  50. Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, and Xiaorui Sun. Universally-optimal distributed shortest paths and transshipment via graph-based 𝓁₁-oblivious routing. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2549-2579. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.100.
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