Document Open Access Logo

Reachability and Shortest Paths in the Broadcast CONGEST Model

Authors Shiri Chechik, Doron Mukhtar

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.11.pdf
  • Filesize: 440 kB
  • 13 pages

Document Identifiers

Author Details

Shiri Chechik
  • Tel Aviv University, Israel
Doron Mukhtar
  • Tel Aviv University, Israel

Cite As Get BibTex

Shiri Chechik and Doron Mukhtar. Reachability and Shortest Paths in the Broadcast CONGEST Model. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.DISC.2019.11

Abstract

In this paper we study the time complexity of the single-source reachability problem and the single-source shortest path problem for directed unweighted graphs in the Broadcast CONGEST model. We focus on the case where the diameter D of the underlying network is constant.
We show that for the case where D = 1 there is, quite surprisingly, a very simple algorithm that solves the reachability problem in 1(!) round. In contrast, for networks with D = 2, we show that any distributed algorithm (possibly randomized) for this problem requires Omega(sqrt{n/ log{n}}) rounds. Our results therefore completely resolve (up to a small polylog factor) the complexity of the single-source reachability problem for a wide range of diameters.
Furthermore, we show that when D = 1, it is even possible to get an almost 3 - approximation for the all-pairs shortest path problem (for directed unweighted graphs) in just 2 rounds. We also prove a stronger lower bound of Omega(sqrt{n}) for the single-source shortest path problem for unweighted directed graphs that holds even when the diameter of the underlying network is 2. As far as we know this is the first lower bound that achieves Omega(sqrt{n}) for this problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed algorithms
  • Broadcast CONGEST
  • distance estimation
  • small diameter

Metrics

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

References

  1. Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n^3/2) Rounds. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC '18), pages 199-205, 2018. Google Scholar
  2. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In Proceedings of the 31st International Symposium on Distributed Computing (DISC '17), pages 7:1-7:16, 2017. Google Scholar
  3. Aaron Bernstein and Danupon Nanongkai. Distributed Exact Weighted All-pairs Shortest Paths in Near-linear Time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC '19), pages 334-342, 2019. Google Scholar
  4. Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. Fast Approximate Shortest Paths in the Congested Clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19), pages 74-83, 2019. Google Scholar
  5. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic Methods in the Congested Clique. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15), pages 143-152, 2015. Google Scholar
  6. 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, 2011. Google Scholar
  7. Michael Elkin. Distributed Exact Shortest Paths in Sublinear Time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC '17), pages 757-770, 2017. Google Scholar
  8. Sebastian Forster and Danupon Nanongkai. A Faster Distributed Single-Source Shortest Paths Algorithm. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS '18), pages 686-697, 2018. Google Scholar
  9. Mohsen Ghaffari and Jason Li. Improved Distributed Algorithms for Exact Shortest Paths. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC'18), pages 431-444, 2018. Google Scholar
  10. Mohsen Ghaffari and Rajan Udwani. Brief Announcement: Distributed Single-Source Reachability. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15), pages 163-165, 2015. Google Scholar
  11. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A Deterministic Almost-tight Distributed Algorithm for Approximating Single-source Shortest Paths. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing (STOC '16), pages 489-498, 2016. Google Scholar
  12. Stephan Holzer and Roger Wattenhofer. Optimal Distributed All Pairs Shortest Paths and Applications. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC '12), pages 355-364, 2012. Google Scholar
  13. Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak. Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^5/4) Rounds. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS '17), pages 168-179, 2017. Google Scholar
  14. Christoph Lenzen and Boaz Patt-Shamir. Fast Partial Distance Estimation and Applications. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15), pages 153-162, 2015. Google Scholar
  15. Christoph Lenzen and David Peleg. Efficient Distributed Source Detection with Limited Bandwidth. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC '13), pages 375-382, 2013. Google Scholar
  16. Danupon Nanongkai. Distributed Approximation Algorithms for Weighted Shortest Paths. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing (STOC '14), pages 565-573, 2014. Google Scholar
  17. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, 2000. 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