More Web Proxy on the site http://driver.im/

research-article

Single-Source Shortest Paths in the CONGEST Model with Improved Bound

Authors:

Doron MukhtarAuthors Info & Claims

PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

Pages 464 - 473

https://doi.org/10.1145/3382734.3405729

Published: 31 July 2020 Publication History

Abstract

We improve the time complexity of the single-source shortest path problem for weighted directed graphs (with non-negative integer weights) in the Broadcast CONGEST model of distributed computing. For polynomially bounded edge weights, the state-of-the-art algorithm for this problem requires [EQUATION] rounds [Forster and Nanongkai, FOCS 2018], which is quite far from the known lower bound of [EQUATION] rounds [Elkin, STOC 2014]; here D is the diameter of the underlying network and n is the number of vertices in it. For the approximate version of this problem, Forster and Nanongkai [FOCS 2018] obtained an upper bound of [EQUATION], and stated that achieving the same bound for the exact case remains a major open problem.

In this paper we resolve the above mentioned problem by devising a new randomized algorithm for solving (the exact version of) this problem in [EQUATION] rounds. Our algorithm is based on a novel weight-modifying technique that allows us to compute bounded-hop distance approximation that preserves a certain form of the triangle inequality for the edges in the graph.

References

[1]

Udit Agarwal and Vijaya Ramachandran. 2019. Distributed Weighted All Pairs Shortest Paths Through Pipelining. In Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS '19). 23--32.

[2]

Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. 2018. 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). 199--205.

Digital Library

[3]

Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen. 2019. Distributed Algorithms for Low Stretch Spanning Trees. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC '19). 4:1--4:14.

[4]

Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In Proceedings of the 31st International Symposium on Distributed Computing (DISC '17). 7:1--7:16.

[5]

Richard Bellman. 1958. On a routing problem. Quart. Appl. Math. 16, 1 (1958), 87--90.

[6]

Aaron Bernstein. 2013. Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs: [Extended Abstract]. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (STOC '13). 725--734.

Digital Library

[7]

Aaron Bernstein and Danupon Nanongkai. 2019. 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). 334--342.

Digital Library

[8]

Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. 2019. Fast Approximate Shortest Paths in the Congested Clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19). 74--83.

Digital Library

[9]

Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. 2015. Algebraic Methods in the Congested Clique. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15). 143--152.

Digital Library

[10]

Shiri Chechik and Doron Mukhtar. 2019. Reachability and Shortest Paths in the Broadcast CONGEST Model. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC '19). 11:1--11:13.

[11]

Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2011. Distributed Verification and Hardness of Distributed Approximation. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (STOC '11). 363--372.

Digital Library

[12]

Michael Elkin. 2004. 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). 331--340.

Digital Library

[13]

Michael Elkin. 2017. Distributed Exact Shortest Paths in Sublinear Time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC '17). 757--770.

Digital Library

[14]

Michael Elkin and Ofer Neiman. 2016. Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS '16). 128--137.

[15]

Orr Fischer and Rotem Oshman. 2019. A Distributed Algorithm for Directed Minimum-Weight Spanning Tree. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC '19). 16:1--16:16.

[16]

Lester R. Ford, Jr. 1956. Network Flow Theory. Technical Report P-923. The RAND Corporation.

[17]

Sebastian Forster and Danupon Nanongkai. 2018. A Faster Distributed Single-Source Shortest Paths Algorithm. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS '18). 686--697.

[18]

Stephan Friedrichs and Christoph Lenzen. 2016. Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '16). 455--466.

Digital Library

[19]

François Le Gall. 2016. Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems. In Proceedings of the 30th International Symposium on Distributed Computing (DISC '16). 57--70.

[20]

Mohsen Ghaffari and Jason Li. 2018. Improved Distributed Algorithms for Exact Shortest Paths. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC'18). 431--444.

Digital Library

[21]

Mohsen Ghaffari and Rajan Udwani. 2015. Brief Announcement: Distributed Single-Source Reachability. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15). 163--165.

Digital Library

[22]

Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2016. 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). 489--498.

Digital Library

[23]

Stephan Holzer and Roger Wattenhofer. 2012. Optimal Distributed All Pairs Shortest Paths and Applications. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC '12). 355--364.

Digital Library

[24]

Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak. 2017. 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). 168--179.

[25]

Philip N. Klein and Sairam Subramanian. 1997. A Randomized Parallel Algorithm for Single-Source Shortest Paths. Journal of Algorithms 25, 2 (1997), 205--220.

Digital Library

[26]

Christoph Lenzen and Boaz Patt-Shamir. 2013. Fast Routing Table Construction Using Small Messages. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (STOC '13). 381--390.

Digital Library

[27]

Christoph Lenzen and Boaz Patt-Shamir. 2015. Fast Partial Distance Estimation and Applications. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15). 153--162.

Digital Library

[28]

Christoph Lenzen and David Peleg. 2013. Efficient Distributed Source Detection with Limited Bandwidth. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC '13). 375--382.

Digital Library

[29]

Aleksander Mądry. 2010. Faster Approximation Schemes for Fractional Multi-commodity Flow Problems via Dynamic Graph Algorithms. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC '10). 121--130.

Digital Library

[30]

Edward F. Moore. 1959. The shortest path through a maze. In Proceedings of an International Symposium on the Theory of Switching, Part II. 285--292.

[31]

Danupon Nanongkai. 2014. Distributed Approximation Algorithms for Weighted Shortest Paths. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing (STOC '14). 565--573.

Digital Library

[32]

David Peleg. 2000. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics.

[33]

David Peleg and Vitaly Rubinovich. 1999. 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). 253--261.

Digital Library

Cited By

Ghaffari MTrygub AKuznetsov PGelles ROlivetti D(2024)A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSPProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662812(401-411)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662812
Cao NFineman JRussell KDhulipala LSun Y(2023)Efficient Construction of Directed Hopsets and Parallel Single-source Shortest Paths (Abstract)Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing10.1145/3597635.3598019(3-4)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3597635.3598019
Rozhoň VHaeupler BMartinsson AGrunau CZuzic GSaha BServedio R(2023)Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate DistancesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585235(321-334)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585235
Show More Cited By

Index Terms

Single-Source Shortest Paths in the CONGEST Model with Improved Bound
1. Networks
  1. Network algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms
    2. Graph algorithms analysis
      1. Shortest paths

Recommendations

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We present a deterministic (1+o(1))-approximation O(n^1/2+o(1)+D^1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (...
Improved distributed algorithms for exact shortest paths
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Computing shortest paths is one of the central problems in the theory of distributed computing. For the last few years, substantial progress has been made on the approximate single source shortest paths problem, culminating in an algorithm of Henzinger, ...
Single-source shortest paths in the CONGEST model with improved bounds
Abstract
Computing shortest paths from a single source is one of the central problems studied in the CONGEST model of distributed computing. After many years in which no algorithmic progress was made, Elkin [STOC ‘17] provided the first improvement over ... $\overset{}{} \sqrt{}^{} \sqrt{}^{}^{}$ $\overset{}{} \sqrt{}$ $\overset{}{} \sqrt{}^{}$ $\overset{}{} \sqrt{}^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

July 2020

539 pages

ISBN:9781450375825

DOI:10.1145/3382734

General Chair:
Yuval Emek
Technion, Israel
,
Program Chair:
Christian Cachin
University of Bern, Switzerland

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '20

Sponsor:

PODC '20: ACM Symposium on Principles of Distributed Computing

August 3 - 7, 2020

Virtual Event, Italy

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
379
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)12

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghaffari MTrygub AKuznetsov PGelles ROlivetti D(2024)A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSPProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662812(401-411)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662812
Cao NFineman JRussell KDhulipala LSun Y(2023)Efficient Construction of Directed Hopsets and Parallel Single-source Shortest Paths (Abstract)Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing10.1145/3597635.3598019(3-4)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3597635.3598019
Rozhoň VHaeupler BMartinsson AGrunau CZuzic GSaha BServedio R(2023)Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate DistancesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585235(321-334)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585235
Rozhoň VGrunau CHaeupler BZuzic GLi JLeonardi SGupta A(2022)Undirected (1+𝜀)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithmsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520074(478-487)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520074
Wu XYao PMilani AWoelfel P(2022)Quantum Complexity of Weighted Diameter and Radius in CONGEST NetworksProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538441(120-130)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538441
Izumi TKitamura NNaruse TSchwartzman GAgrawal KLee I(2022)Fully Polynomial-Time Distributed Computation in Low-Treewidth GraphsProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538590(11-22)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538590
Blikstad JVan Den Brand JEfron YMukhopadhyay SNanongkai D(2022)Nearly Optimal Communication and Query Complexity of Bipartite Matching2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00113(1174-1185)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00113
Forster SGoranci GLiu YPeng RSun XYe M(2022)Minor Sparsifiers and the Distributed Laplacian Paradigm2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00099(989-999)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00099
Cao NFineman JRussell KMiller ACensor-Hillel K(2021)Brief AnnouncementProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467945(493-496)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467945
Fischer OOshman R(2021)A distributed algorithm for directed minimum-weight spanning treeDistributed Computing10.1007/s00446-021-00398-336:1(57-87)Online publication date: 29-Jun-2021
https://doi.org/10.1007/s00446-021-00398-3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents