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

research-article

Near-Optimal Distributed Routing with Low Memory

Authors:

Ofer NeimanAuthors Info & Claims

PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

Pages 207 - 216

https://doi.org/10.1145/3212734.3212761

Published: 23 July 2018 Publication History

Abstract

Distributed \em routing is one of the most central and fundamental problems in the area of Distributed Graph Algorithms. It was extensively studied for almost thirty years. Nevertheless, the currently existing solutions for this problem require either prohibitively large construction (aka preprocessing) time, or prohibitively large memory usage either during the construction or during the routing phase, and suffer from suboptimal labels and tables' sizes. We devise a distributed routing scheme that enjoys the best of all worlds. Specifically, its construction time and memory requirements during the construction phase are near-optimal, and so is also the tradeoff between the sizes of routing tables and labels on the one hand, and the stretch on the other. On the way to this result, we also improve upon existing solutions for the distributed exact \em tree routing problem. Previous solutions require Ω(√ ) memory, and provide tables and labels of size O(log n) and O(log^2 n), respectively. Our solution, on the other hand, requires just O(log n) memory, and has tables of size O(1), and labels of size O(log n). These bounds match the bounds of the best-known centralized solution.

References

[1]

Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi . 2004. Routing with Improved Communication-Space Trade-Off Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4--7, 2004, Proceedings. 305--319.

[2]

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup . 2008. Compact Name-independent Routing with Minimum Stretch. ACM Trans. Algorithms Vol. 4, 3, Article bibinfoarticleno37 (July . 2008), bibinfonumpages12 pages.

Digital Library

[3]

Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg . 1990. Improved Routing Strategies with Succinct Tables. J. Algorithms Vol. 11, 3 (Sept. . 1990), 307--341.

Digital Library

[4]

B. Awerbuch and D. Peleg . 1992. Routing with polynomial communication-space tradeoff. SIAM J. Discrete Mathematics Vol. 5 (1992), 151--162.

Digital Library

[5]

Shiri Chechik . 2013. Compact routing schemes with improved stretch. In ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22--24, 2013. 33--41.

Digital Library

[6]

Lenore Cowen . 2001. Compact Routing with Minimum Stretch. J. Algorithms Vol. 38, 1 (2001), 170--183.

Digital Library

[7]

Tamar Eilam, Cyril Gavoille, and David Peleg . 2003. Compact routing schemes with low stretch factor. J. Algorithms Vol. 46, 2 (2003), 97--114.

Digital Library

[8]

Michael Elkin . 2017. Distributed Exact Shortest Paths in Sublinear Time Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017). ACM, New York, NY, USA, 757--770.

Digital Library

[9]

Michael Elkin and Ofer Neiman . 2016 a. Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9--11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. 128--137.

[10]

Michael Elkin and Ofer Neiman . 2016 b. On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16). ACM, New York, NY, USA, 235--244.

Digital Library

[11]

Michael Elkin and Ofer Neiman . 2017 a. Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC. To be published.

[12]

Michael Elkin and Ofer Neiman . 2017 b. Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR Vol. abs/1704.08468 (2017). deftempurl%http://arxiv.org/abs/1704.08468 tempurl

[13]

Cyril Gavoille and David Peleg . 2003. Compact and localized distributed data structures. Distributed Computing Vol. 16, 2--3 (2003), 111--120.

Digital Library

[14]

Christoph Lenzen and Boaz Patt-Shamir . 2013. Fast routing table construction using small messages Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1--4, 2013. 381--390.

Digital Library

[15]

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 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015. 153--162.

Digital Library

[16]

Christoph Lenzen and Boaz Patt-Shamir . 2016. Personal communication.

[17]

Christoph Lenzen, Boaz Patt-Shamir, and David Peleg . 2016. Distributed Distance Computation and Routing with Small Messages. manuscript.

[18]

Danupon Nanongkai . 2014. Distributed approximation algorithms for weighted shortest paths Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 565--573.

Digital Library

[19]

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

Digital Library

[20]

David Peleg and Eli Upfal . 1989. A trade-off between space and efficiency for routing tables. J. ACM Vol. 36, 3 (1989), 510--530.

Digital Library

[21]

Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer . 2012. Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. Vol. 41, 5 (2012), 1235--1265.

Digital Library

[22]

M. Thorup and U. Zwick . 2001 a. Approximate Distance Oracles. In Proc. of the 33rd ACM Symp. on Theory of Computing. 183--192.

Digital Library

[23]

Mikkel Thorup and Uri Zwick . 2001 b. Compact Routing Schemes. In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '01). ACM, New York, NY, USA, 1--10.

Digital Library

Cited By

Dou JGötte THillebrandt HScheideler CWerthmann JOshman RNolin AHalldorsson MBalliu A(2023)Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar GraphsProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594561(67-70)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594561
Elkin MNeiman O(2022)Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNCDistributed Computing10.1007/s00446-022-00431-z35:5(419-437)Online publication date: 29-Jun-2022
https://doi.org/10.1007/s00446-022-00431-z
Elkin MFiltser ANeiman OEmek YCachin C(2020)Distributed Construction of Light NetworksProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405701(483-492)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405701
Show More Cited By

Index Terms

Near-Optimal Distributed Routing with Low Memory
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
    2. Distributed algorithms

Recommendations

Near-optimal Distributed Triangle Enumeration via Expander Decompositions
We present improved distributed algorithms for variants of the triangle finding problem in the model. We show that triangle detection, counting, and enumeration can be solved in rounds using expander decompositions. This matches the triangle enumeration ...
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity)...
Compact routing with slack in low doubling dimension
PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing
We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek name-independent routing schemes with (1+ε) stretch and polylogarithmic storage at each node: since existing lower bound precludes such a scheme,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

July 2018

512 pages

ISBN:9781450357951

DOI:10.1145/3212734

General Chairs:
Calvin Newport
Georgetown University, USA
,
Idit Keidar
Technion, Israel

Copyright © 2018 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]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

PODC '18

PODC '18: ACM Symposium on Principles of Distributed Computing

July 23 - 27, 2018

Egham, United Kingdom

Acceptance Rates

PODC '18 Paper Acceptance Rate 41 of 163 submissions, 25%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
120
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)5

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dou JGötte THillebrandt HScheideler CWerthmann JOshman RNolin AHalldorsson MBalliu A(2023)Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar GraphsProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594561(67-70)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594561
Elkin MNeiman O(2022)Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNCDistributed Computing10.1007/s00446-022-00431-z35:5(419-437)Online publication date: 29-Jun-2022
https://doi.org/10.1007/s00446-022-00431-z
Elkin MFiltser ANeiman OEmek YCachin C(2020)Distributed Construction of Light NetworksProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405701(483-492)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405701
Castañeda ALefévre JTrehan A(2020)Fully Compact Routing in Low Memory Self-Healing TreesProceedings of the 21st International Conference on Distributed Computing and Networking10.1145/3369740.3369786(1-10)Online publication date: 4-Jan-2020
https://dl.acm.org/doi/10.1145/3369740.3369786
Elkin MNeiman OScheideler CBerenbrink P(2019)Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNCThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323177(333-341)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323177

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