Document Open Access Logo

Sparse Hopsets in Congested Clique

Author Yasamin Nazari

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.34.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

Yasamin Nazari
  • Johns Hopkins University, Baltimore, MD, United States

Funding

This work supported is in part by NSF awards CCF-1464239 and CCF-1909111.

Acknowledgements

The author would like to thank Michael Dinitz and Goran Zuzic for helpful discussions.

Cite As Get BibTex

Yasamin Nazari. Sparse Hopsets in Congested Clique. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.OPODIS.2019.34

Abstract

We give the first Congested Clique algorithm that computes a sparse hopset with polylogarithmic hopbound in polylogarithmic time. Given a graph G=(V,E), a (β,ε)-hopset H with "hopbound" β, is a set of edges added to G such that for any pair of nodes u and v in G there is a path with at most β hops in G ∪ H with length within (1+ε) of the shortest path between u and v in G. Our hopsets are significantly sparser than the recent construction of [Censor-Hillel et al., 2019], that constructs a hopset of size Õ (n^{3/2}), but with a smaller polylogarithmic hopbound. On the other hand, the previously known construction of sparse hopsets with polylogarithmic hopbound in the Congested Clique model, proposed by [Elkin and Neiman, 2018; Elkin and Neiman, 2019; Elkin and Neiman, 2019], all require polynomial rounds. 
One tool that we use is an efficient algorithm that constructs an l-limited neighborhood cover, that may be of independent interest. Finally, as a side result, we also give a hopset construction in a variant of the low-memory Massively Parallel Computation model, with improved running time over existing algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Hopsets
  • Congested Clique
  • Shortest Paths
  • Massively Parallel Computation

Metrics

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

References

  1. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. SIAM Journal on Computing, 2018. Google Scholar
  2. Baruch Awerbuch and David Peleg. Sparse partitions. In Proceedings of the Symposium on Foundations of Computer Science. IEEE, 1990. Google Scholar
  3. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the Symposium on Principles of Database Systems. ACM, 2013. Google Scholar
  4. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing, 2017. Google Scholar
  5. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Brief Announcement: Semi-MapReduce Meets Congested Clique. arXiv preprint arXiv:1802.10297, 2018. Google Scholar
  6. Keren Censor-Hillel, Michal Dory, Janne H Korhonen, and Dean Leitersdorf. Fast Approximate Shortest Paths in the Congested Clique. In Proceedings of the Symposium on Principles of Distributed Computing. ACM, 2019. Google Scholar
  7. Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 1998. Google Scholar
  8. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM), 2000. Google Scholar
  9. Michael Dinitz and Yasamin Nazari. Massively Parallel Approximate Distance Sketches. OPODIS, 2019. Google Scholar
  10. Michael Elkin and Ofer Neiman. Near-Optimal Distributed Routing with Low Memory. In Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, 2018. Google Scholar
  11. Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. SIAM Journal on Computing, 2019. Google Scholar
  12. Michael Elkin and Ofer Neiman. Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures. ACM, 2019. Google Scholar
  13. Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In Proceedings of the International Symposium on Algorithms and Computation. Springer, 2011. Google Scholar
  14. James W Hegeman and Sriram V Pemmaraju. Lessons from the congested clique applied to MapReduce. Theoretical Computer Science, 2015. Google Scholar
  15. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the Symposium on Theory of Computing. ACM, 2016. Google Scholar
  16. Shang-En Huang and Seth Pettie. Thorup-Zwick emulators are universally optimal hopsets. Information Processing Letters, 2019. Google Scholar
  17. Philip N Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 1997. Google Scholar
  18. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proceedings of the ACM Symposium on Principles of Distributed computing. ACM, 2013. Google Scholar
  19. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in O(loglog n) communication rounds. SIAM Journal on Computing, 2005. Google Scholar
  20. Gary L Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved Parallel Algorithms for Spanners and Hopsets. In Proceedings of the Symposium on Parallelism in Algorithms and Architectures. ACM, 2015. Google Scholar
  21. Gary L Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the ACM Symposium on Parallelism in algorithms and architectures. ACM, 2013. Google Scholar
  22. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proceedings of the ACM Symposium on Theory of Computing. ACM, 2014. Google Scholar
  23. Merav Parter and Eylon Yogev. Low congestion cycle covers and their applications. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2019. Google Scholar
  24. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM), 2005. 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