announcement

Brief Announcement: Distributed Single-Source Reachability

Authors:

Mohsen Ghaffari,

Rajan UdwaniAuthors Info & Claims

PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

Pages 163 - 165

https://doi.org/10.1145/2767386.2767444

Published: 21 July 2015 Publication History

Get Access

Abstract

In the directed single-source reachability problem, input is a directed graph G=(V, E) and a source node s, and the objective is to identify nodes t for which there is a directed path in G from s to t. Recently Nanongkai[STOC'14] presented a distributed algorithm that solves this problem in Õ(D+√nD^1/2) rounds, where D and n respectively denote the network diameter and the number of nodes. This note presents an algorithm that slightly improves the round complexity to Õ(D+√nD^1/4), thus getting closer to the ~Ω(D+√n) lower bound of Das Sarma et al.[STOC'11]

References

[1]

A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed verification and hardness of distributed approximation. In Proc. of the Symp. on Theory of Comp. (STOC), pages 363--372, 2011.

Digital Library

Google Scholar

[2]

D. Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proc. of the Symp. on Theory of Comp. (STOC), pages 565--573. ACM, 2014.

Digital Library

Google Scholar

[3]

D. Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

Crossref

Google Scholar

Cited By

View all

Manoharan VRamachandran V(2024)Computing Replacement Paths in the CONGEST ModelStructural Information and Communication Complexity10.1007/978-3-031-60603-8_23(420-437)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_23
Jiang YMukhopadhyay SSaha BServedio R(2023)Finding a Small Vertex Cut on Distributed NetworksProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585201(1791-1801)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585201
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
Show More Cited By

Index Terms

Brief Announcement: Distributed Single-Source Reachability
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially ...
Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-...
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

We give a randomness-efficient Massively Parallel Computation (MPC) algorithm for deciding whether an undirected graph is connected. For Connectivity on n-vertex, m-edge graphs whose components have diameter at most D = 2o(log n/ log log n), our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

July 2015

508 pages

ISBN:9781450336178

DOI:10.1145/2767386

General Chair:
Chryssis Georgiou
University of Cyprus, Cyprus
,
Program Chair:
Paul G. Spirakis
University of Liverpool, UK & CTI, Greece

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2015

Check for updates

Author Tags

Qualifiers

Announcement

Conference

PODC '15

Sponsor:

PODC '15: ACM Symposium on Principles of Distributed Computing

July 21 - 23, 2015

Donostia-San Sebastián, Spain

Acceptance Rates

PODC '15 Paper Acceptance Rate 45 of 191 submissions, 24%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
196
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)3

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Manoharan VRamachandran V(2024)Computing Replacement Paths in the CONGEST ModelStructural Information and Communication Complexity10.1007/978-3-031-60603-8_23(420-437)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_23
Jiang YMukhopadhyay SSaha BServedio R(2023)Finding a Small Vertex Cut on Distributed NetworksProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585201(1791-1801)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585201
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
Chechik SMukhtar D(2022)Single-source shortest paths in the CONGEST model with improved boundsDistributed Computing10.1007/s00446-021-00412-835:4(357-374)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s00446-021-00412-8
Bernstein ANanongkai D(2021)Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear TimeSIAM Journal on Computing10.1137/20M131278252:2(STOC19-112-STOC19-127)Online publication date: 23-Nov-2021
https://doi.org/10.1137/20M1312782
Chechik SMukhtar DEmek YCachin C(2020)Single-Source Shortest Paths in the CONGEST Model with Improved BoundProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405729(464-473)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405729
Liu YJambulapati ASidford A(2019)Parallel Reachability in Almost Linear Work and Square Root Depth2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00098(1664-1686)Online publication date: Nov-2019
https://doi.org/10.1109/FOCS.2019.00098
Forster SNanongkai D(2018)A Faster Distributed Single-Source Shortest Paths Algorithm2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2018.00071(686-697)Online publication date: Oct-2018
https://doi.org/10.1109/FOCS.2018.00071
Huang CNanongkai DSaranurak T(2017)Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^{5/4}) Rounds2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2017.24(168-179)Online publication date: Oct-2017
https://doi.org/10.1109/FOCS.2017.24

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets

Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity