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

Article

A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners

Author:

Michael ElkinAuthors Info & Claims

PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing

Pages 185 - 194

https://doi.org/10.1145/1281100.1281128

Published: 12 August 2007 Publication History

Abstract

Currently, there are no known explicit algorithms for the great majority of graph problems in the dynamic distributed message-passing model. Instead, most state-of-the-art dynamic distributed algorithms are constructed by composing a static algorithm for the problem at hand with a simulation technique that converts static algorithms to dynamic ones. We argue that this powerful methodology does not provide satisfactory solutions for many important dynamic distributed problems, and this necessitates developing algorithms for these problems from scratch.

In this paper we develop a fully dynamic distributed algorithm for maintaining sparse spanners. Our algorithm improves drastically the quiescence time of the state-of-the-art algorithm for the problem. Moreover, we show that the quiescence time of our algorithm is optimal up to a small constant factor. In addition, our algorithm improves significantly upon the state-of-the-art algorithm in all efficiency parameters, specifically, it has smaller quiescence message and space complexities, and smaller local processing time. Finally, our algorithm is self-contained and fairly simple, and is, consequently, amenable to implementation on unsophisticated network devices.

References

[1]

Y. Afek, B. Awerbuch, and E. Gafni. Applying static network protocols to dynamic networks. In Proc. 28th Symp. on Foundations of Computer Science, pages 358--370, 1987.

Digital Library

[2]

Y. Afek, B. Awerbuch, S. Plotkin, and M. Saks. Local management of a global resource in a communication network. In Proc. of the 28th IEEE Annual Symp. on Foundations of Computer Science, pages 347--357, 1987.

Digital Library

[3]

Y. Afek, E. Gafni, and M. Ricklin. Upper and lower bounds for routing schemes in dynamic networks. In Proc. of 30th IEEE Annual Symposium on Foundations of Computer Science (FOCS-89), pages 370--375, 1989.

Digital Library

[4]

Y. Afek, E. Gafni, and A. Rosen. The slide mechanism with applications in dynamic networks. In Proc. of the 11th ACM Symp. Principles of Distributed Computing, pages 35--46, 1992.

Digital Library

[5]

B. Awerbuch. Complexity of network synchronization. J. ACM, 4:804--823, 1985.

Digital Library

[6]

B. Awerbuch, I. Cidon, and S. Kutten. Communication-optimal maintenance of replicated information. In Proc. IEEE Symp. on Foundations of Computer Science, pages 492--502, 1990.

Digital Library

[7]

B. Awerbuch and S. Even. Reliable broadcast protocols in unreliable networks. Networks, 16:381--396, 1986.

[8]

B. Awerbuch, O. Goldreich, and A. Herzberg. A quintitive approach to dynamic networks. In Proc. of the 9th ACM Symp. on Principles of Distributed Computing, pages 189--203, 1990.

Digital Library

[9]

B. Awerbuch, S. Kutten, and D. Peleg. Online load balancing in a distributed network. In Proc. 24th ACM Symp. on Theory of Comput., pages 571--580, 1992.

[10]

B. Awerbuch, B. Patt-Shamir, D. Peleg, and M. E. Saks. Adapting to asynchronous dynamic networks. In Proc. of the 24th Annual ACM Symp. on Theory of Computing, pages 557--570, 1992.

Digital Library

[11]

B. Awerbuch, B. Patt-Shamir, and G. Varghese. Self-stabilization by local cheking and correction. In Proc. 32nd IEEE Symp. on Foundations of Computer Science, pages 268--277, 1991.

Digital Library

[12]

B. Awerbuch and D. Peleg. Network synchronization with polylogarithmic overhead. In Proc. 31st IEEE Symp. on Foundations of Computer Science, pages 514--522, 1990.

Digital Library

[13]

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

Digital Library

[14]

B. Awerbuch and M. Sipser. Dynamic networks are as fast as static networks. In Proc. 29th IEEE Symp. on Foundations of Computer Science, pages 206--220, 1988.

Digital Library

[15]

S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie. New constructions of (a,b)-spanners and additive spanners. In SODA: ACM-SIAM Symposium on Discrete Algorithms, pages 672--681, 2005.

Digital Library

[16]

S. Baswana and S. Sen. A simple linear time algorithm for computing a (2k - 1)-spanner of O(n ^1+1/k) size in weighted graphs. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming, volume 2719 of LNCS, pages 384--396. Springer, 2003.

Digital Library

[17]

S. Cicerone, G. D. Stefano, and M. Flammini. Static and dynamic low-congested interval routing schemes. Theoretical Computer Science, 276:315--354, 2002.

Digital Library

[18]

S. Cicerone, G. D. Stefano, D. Frigione, and U. Nanni. A fully dynamic algorithm for distributed shortest paths. Theoretical Computer Science, 297:83--102, 2003.

Digital Library

[19]

E. Cohen. Fast algorithms for t-spanners and stretch-t paths. SIAM J. Comput., 28:210--236, 1999.

Digital Library

[20]

S. Dolev. Self-Stabilization. MIT Press, 2000.

Digital Library

[21]

M. Elkin. Computing almost shortest paths. In Proc. 20th ACM Symp. on Principles of Distributed Computing, pages 53--62, 2001.

Digital Library

[22]

M. Elkin. A streaming and fully dynamic centralized algorithm for maintaining sparse spanners. In Proc. of the Internat. Colloq. Autonata, Languages, and Progr. (to appear), 2007.

Digital Library

[23]

M. Elkin and J. Zhang. Efficient algorithms for constructing (1 + ε, ß)-spanners in the distributed and streaming models. Distributed Computing, 18:375--385, 2006.

Digital Library

[24]

P. Erdõs. Extremal problems in graph theory. In Theory of Graphs and Applications (Proc. Sympos. Smolenice), pages 29--36, 1964.

[25]

J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. Graph distances in the streaming model: The value of space. In Proc. of the ACM-SIAM Symp. on Discrete Algorithms, pages 745--754, 2005.

Digital Library

[26]

P. Humblet. Another adaptive distributed shortest path algorithm. IEEE Transactions on Communications, 39(6):995--1003, 1991.

[27]

G. F. Italiano. Distributed algorithms for updating shortest paths. In Proc. Intern. Workshop on Distributed Algorithms, pages 200--211, 1991.

Digital Library

[28]

A. Korman and D. Peleg. Labeling schemes for weighted dynamic trees. In Proc. 30th Int. Colloq. on Automata, Languages and Programming, pages 369--383, 2003.

Digital Library

[29]

A. Korman, D. Peleg, and Y. Rodeh. Labeling schemes for dynamic tree networks. Theory of Computing Systems, 37:49--75, 2004.

[30]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. The price of being near-sighted. Proc. of Symp. on Discrete Algorithms, pages 980--989, 2006.

Digital Library

[31]

N. Linial and M. Saks. Decomposing graphs into regions of small diameter. Combinatorica, 13:441--454, 1993.

[32]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.

Digital Library

[33]

D. Peleg and J. D. Ullman. An optimal synchronizer for the hypercube. SIAM J. on Comput., 18:740--747, 1989.

Digital Library

[34]

D. Peleg and E. Upfal. A tradeoff between size and efficiency for routing tables. J. of the ACM, 36:510--530, 1989.

Digital Library

[35]

W. B. Powell, P. Jaillet, and A. Odoni. Stochastic and dynamic networks and routing. In M. O. Ball and T. L. Magnanti and C. L. Monma and and G. L. Nemhauser (editors) Network Routing: volume 8 of Handbooks in Operations Research and Management Science, pages 141--295, 1995.

[36]

K. V. S. Ramarao and S. Venkatesan. On finding and updating shortest paths distributively. Journal of Algorithms, 13:235--257, 1992.

Digital Library

[37]

M. Thorup and U. Zwick. Approximate distance oracles. In Proc. of the 33rd ACM Symp. on Theory of Computing, pages 183--192, 2001.

Digital Library

[38]

M. Thorup and U. Zwick. Compact routing schemes. In Proc. of the 13th Symp. on Parallelism in Algorithms and Architectures, pages 1--10, 2001.

Digital Library

Cited By

Bezdrighin MElkin MGhaffari MGrunau CHaeupler BIlchi SRozhoň VAgrawal KLee I(2022)Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity CertificatesProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538565(1-10)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538565
Robinson PMarx D(2021)Being fast means being chattyProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458190(2105-2120)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458190
Dory MFischer OKhoury SLeitersdorf DMiller ACensor-Hillel K(2021)Constant-Round Spanners and Shortest Paths in Congested Clique and MPCProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467928(223-233)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467928
Show More Cited By

Index Terms

A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Fully dynamic randomized algorithms for graph spanners

Spanner of an undirected graph G = (V,E) is a subgraph that is sparse and yet preserves all-pairs distances approximately. More formally, a spanner with stretch t ∈ ℕ is a subgraph (V,E_S), E_S ⊆ E such that the distance between any two vertices in the ...
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners

We present a streaming algorithm for constructing sparse spanners and show that our algorithm significantly outperforms the state-of-the-art algorithm for this task (due to Feigenbaum et al.). Specifically, the processing time per edge of our algorithm ...
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
ICALP'07: Proceedings of the 34th international conference on Automata, Languages and Programming

We present a streaming algorithm for constructing sparse spanners and show that our algorithm out-performs significantly the state-of-the-art algorithm for this task [20]. Specifically, the processing time-per-edge of our algorithm is drastically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing

August 2007

424 pages

ISBN:9781595936165

DOI:10.1145/1281100

General Chair:
Indranil Gupta
UIUC, USA
,
Program Chair:
Rogert Wattenhofer
ETH Zurich, Switzerland

Copyright © 2007 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: 12 August 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC07

Sponsor:

PODC07: ACM Symposium on Principles of Distributed Computing 2007

August 12 - 15, 2007

Oregon, Portland, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
293
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bezdrighin MElkin MGhaffari MGrunau CHaeupler BIlchi SRozhoň VAgrawal KLee I(2022)Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity CertificatesProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538565(1-10)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538565
Robinson PMarx D(2021)Being fast means being chattyProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458190(2105-2120)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458190
Dory MFischer OKhoury SLeitersdorf DMiller ACensor-Hillel K(2021)Constant-Round Spanners and Shortest Paths in Congested Clique and MPCProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467928(223-233)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467928
Foerster KKorhonen JPaz ARybicki JSchmid S(2021)Input-Dynamic Distributed Algorithms for Communication NetworksProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34473845:1(1-33)Online publication date: 22-Feb-2021
https://dl.acm.org/doi/10.1145/3447384
Casteigts APeters JSchoeters J(2021)Temporal cliques admit sparse spannersJournal of Computer and System Sciences10.1016/j.jcss.2021.04.004121(1-17)Online publication date: Nov-2021
https://doi.org/10.1016/j.jcss.2021.04.004
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
Censor-Hillel KParter MSchwartzman G(2020)Derandomizing local distributed algorithms under bandwidth restrictionsDistributed Computing10.1007/s00446-020-00376-1Online publication date: 18-Apr-2020
https://doi.org/10.1007/s00446-020-00376-1
Khan S(2019)Near Optimal Parallel Algorithms for Dynamic DFS in Undirected GraphsACM Transactions on Parallel Computing10.1145/33642126:3(1-33)Online publication date: 2-Nov-2019
https://dl.acm.org/doi/10.1145/3364212
Elkin MMatar SRobinson PEllen F(2019)Near-Additive Spanners In Low Polynomial Deterministic CONGEST TimeProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331635(531-540)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331635
Elkin MNeiman O(2018)Efficient Algorithms for Constructing Very Sparse Spanners and EmulatorsACM Transactions on Algorithms10.1145/327465115:1(1-29)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3274651
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