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

research-article

DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead

Authors:

Gopal Pandurangan,

Peter Robinson,

Amitabh TrehanAuthors Info & Claims

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

Pages 438 - 447

https://doi.org/10.1145/3382734.3405716

Published: 31 July 2020 Publication History

Abstract

With the rise of dynamic reconfigurable networks such as Peer-to-Peer (P2P) networks, overlay networks, ad hoc wireless and mesh networks, it has become important to construct and maintain topologies with various desirable properties (such as connectivity, low diameter, expansion, low degree etc.) in an efficient decentralized manner. The main result of this paper is a distributed protocol called DConstructor that given any (connected) network topology will "converge" to a given (desired) target topology such as an expander, hypercube, or Chord, with high probability. Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead (where n is the network size) for topology construction and maintenance: only polylogarithmic (in n) bits need to be processed and sent by each node per round, the convergence time is polylogarithmic rounds and any node's computation cost per round is also polylogarithmic. Our protocol is robust and self-repairing in the sense that it will converge to the desired topology in polylogarithmic rounds and polylogarithmic communication cost under dynamic topology changes and arbitrary insertions and deletions of nodes.

References

[1]

Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, and Yitong Yin. 2005. Fast Construction of Overlay Networks. In SPAA 2005. 145--154.

[2]

James Aspnes and Gauri Shah. 2007. Skip graphs. ACM Transactions on Algorithms 3, 4 (Nov. 2007), 37.

Digital Library

[3]

James Aspnes and Gauri Shah. 2007. Skip graphs. ACM Trans. Algorithms 3, 4 (2007), 37.

Digital Library

[4]

Hagit Attiya and Jennifer Welch. 2004. Distributed Computing: Fundamentals, Simulations and Advanced Topics. Wiley & Sons.

Digital Library

[5]

J Augustine, G Pandurangan, and P Robinson. 2016. Distributed Algorithmic Foundations of Dynamic Networks. SIGACT News 47, 1 (2016), 69--98.

Digital Library

[6]

J Augustine, G Pandurangan, P Robinson, and E Upfal. 2012. Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks. In SODA.

[7]

Baruch Awerbuch and Christian Scheideler. 2009. Towards a Scalable and Robust DHT. Theory of Computing Systems 45 (2009), 234--260. Issue 2.

Digital Library

[8]

S Baswana and S Sen. 2003. A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n^1+1/k) Size in Weighted Graphs. In ICALP. 384--296.

[9]

A Berns and S Ghosh. 2009. Dissecting Self-^* Properties. Self-Adaptive and Self-Organizing Systems, International Conference on 0 (2009), 10--19.

[10]

A Berns, S Ghosh, and S V Pemmaraju. 2013. Building self-stabilizing overlay networks with the transitive closure framework. Theor. Comput. Sci. 512 (2013), 2--14.

Digital Library

[11]

Armando Castañeda, Danny Dolev, and Amitabh Trehan. [n.d.]. Compact routing messages in self-healing trees. In ICDCN 2016.

Digital Library

[12]

Colin Cooper, Martin Dyer, and Andrew J. Handley. 2009. The flip markov chain and a randomising P2P protocol. In PODC. ACM.

[13]

A. Das Sarma, A. Molla, and G. Pandurangan. 2012. Fast Distributed Computation in Dynamic Networks via Random Walks. In DISC.

[14]

Atish Das Sarma, Danupon Nanongkai, and Gopal Pandurangan. 2009. Fast distributed random walks. In PODC. 161--170.

[15]

Michael Elkin. 2007. A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In PODC. 185--194.

[16]

Seth Gilbert, Gopal Pandurangan, Peter Robinson, and Amitabh Trehan. 2020. DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead. to appear on arXiv (2020).

[17]

C. Gkantsidis, M. Mihail, and A. Saberi. 2006. Random Walks in Peer-to-Peer Networks: Algorithms and Evaluation. Performance Evaluation 63(3) (2006), 241--263.

[18]

T Hayes, N Rustagi, J Saia, and A Trehan. [n.d.]. The forgiving tree: a self-healing distributed data structure. In PODC '08. 203--212.

[19]

T Hayes, J Saia, and A Trehan. 2012. The Forgiving Graph: a distributed data structure for low stretch under adversarial attack. Distributed Computing (2012), 1--18.

[20]

Shlomo Hoory, Nathan Linial, and Avi Wigderson. 2006. Expander graphs and their applications. Bulletin of the AMS 43, 04 (2006), 439--562.

[21]

R Jacob, A Richa, C Scheideler, S Schmid, and H Täubig. 2014. SKIP+: A Self-Stabilizing Skip Graph. J. ACM 61, 6, Article 36 (Dec. 2014), 26 pages.

Digital Library

[22]

Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. 2006. Towards Secure and Scalable Computation in Peer-to-Peer Networks. In FOCS. 87--98.

[23]

Sebastian Kniesburges, Andreas Koutsopoulos, and Christian Scheideler. [n.d.]. Re-Chord: a self-stabilizing chord overlay network (SPAA '11). 235--244.

[24]

Fabian Kuhn, Stefan Schmid, and Roger Wattenhofer. 2005. A Self-repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn. In IPTPS. 13--23.

[25]

F Kuhn, S Schmid, and R Wattenhofer. 2010. Towards worst-case churn resistant peer-to-peer systems. Distributed Computing 22, 4 (2010), 249--267.

Digital Library

[26]

Shay Kutten and Avner Porat. 1999. Maintenance of a Spanning Tree in Dynamic Networks. In Distributed Computing. Vol. 1693. 846--846.

[27]

C. Law and K.-Y. Siu. 2003. Distributed construction of random expander networks. In INFOCOM 2003, Vol. 3.

[28]

D A Levin and Y Peres. 2017. Markov chains and mixing times. Vol. 107. American Mathematical Soc.

[29]

Alexander Lubotzky. 1994. Discrete groups, expanding graphs and invariant measures, vol. 125. Progress in Mathematics. Basel: Birkhäuser Verlag (1994).

[30]

Michael Luby. 1986. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 4 (1986), 1036--1053.

Digital Library

[31]

N. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann.

[32]

R Melamed and I Keidar. 2008. Araneola: A scalable reliable multicast system for dynamic environments. J. Parallel Distrib. Comput. 68, 12 (2008), 1539--1560.

Digital Library

[33]

Moni Naor and Udi Wieder. 2007. Novel architectures for P2P applications: The continuous-discrete approach. ACM Transactions on Algorithms 3, 3 (2007).

Digital Library

[34]

Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal. 2001. Building Low-Diameter P2P Networks. In FOCS. 492--499.

[35]

Gopal Pandurangan, Peter Robinson, and Amitabh Trehan. 2016. DEX: self-healing expanders. Distributed Computing 29, 3 (2016), 163--185.

Digital Library

[36]

G Pandurangan and A Trehan. 2014. Xheal: a localized self-healing algorithm using expanders. Distributed Computing 27, 1 (2014), 39--54.

Digital Library

[37]

David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics ans Applications, Philadelphia.

[38]

S Ratnasamy, P Francis, M Handley, R Karp, and S Shenker. 2001. A scalable content-addressable network. SIGCOMM Comput. Commun. Rev. 31 (2001), 161--172. Issue 4.

Digital Library

[39]

O Reingold, S Vadhan, and A Wigderson. 2000. Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. In Annals of Mathematics. 157--187.

[40]

M.K. Reiter, A. Samar, and C. Wang. 2005. Distributed construction of a fault-tolerant network from a tree. In SRDS. 155 -- 165.

[41]

A I T Rowstron and P Druschel. 2001. Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. In Int. Conf. on Distributed Systems Platforms. 329--350.

[42]

Jared Saia and Amitabh Trehan. 2008. Picking up the Pieces: Self-Healing in reconfigurable networks. In IPDPS.

[43]

Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. 2013. Distributed Random Walks. J. ACM 60, 1 (2013), 2:1--2:31.

[44]

Atish Das Sarma and Amitabh Trehan. 2012. Edge-preserving self-healing: keeping network backbones densely connected. In Workshop on Network Science for Communication Networks (NetSciCom 2012), IEEE InfoComm. IEEE Xplore.

[45]

J-A Serret. 1850. Mémoire sur le nombre de valeurs que peut prendre une fonction quand on permute les lettres qu'elle renferme. Journal de mathématiques pures et appliquées (1850), 1--44.

[46]

I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. 2001. Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications. ACM SIGCOMM Conference (2001), 149--160.

[47]

I Stoica, R Morris, D Liben-Nowell, D R Karger, M F Kaashoek, F Dabek, and H Balakrishnan. 2003. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw. 11, 1 (2003), 17--32.

Digital Library

[48]

Amitabh Trehan. 2010. Algorithms for self-healing networks. Dissertation. University of New Mexico.

[49]

A Trehan. 2012. Self-healing using virtual structures. CoRR abs/1202.2466 (2012).

[50]

B.Y. Zhao, Ling Huang, J. Stribling, S.C. Rhea, A.D. Joseph, and J.D. Kubiatowicz. 2004. Tapestry: a resilient global-scale overlay for service deployment. Selected Areas in Communications, IEEE Journal on 22, 1 (2004), 41 -- 53.

Cited By

Mertzios GMichail OSkretas GSpirakis PTheofilatos M(2024)The complexity of growing a graphJournal of Computer and System Sciences10.1016/j.jcss.2024.103587(103587)Online publication date: Sep-2024
https://doi.org/10.1016/j.jcss.2024.103587
Götte THinnenthal KScheideler CWerthmann J(2023)Time-optimal construction of overlay networksDistributed Computing10.1007/s00446-023-00442-436:3(313-347)Online publication date: 15-Feb-2023
https://doi.org/10.1007/s00446-023-00442-4
Mertzios GMichail OSkretas GSpirakis PTheofilatos M(2022)The Complexity of Growing a GraphAlgorithmics of Wireless Networks10.1007/978-3-031-22050-0_9(123-137)Online publication date: 13-Dec-2022
https://doi.org/10.1007/978-3-031-22050-0_9
Show More Cited By

Index Terms

DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Time-Optimal Construction of Overlay Networks
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

We show how to construct an overlay network of constant degree and diameter O(log n) in time O(log n) starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know ...
Time-optimal construction of overlay networks
Abstract
This article shows how to construct an overlay network of constant degree and diameter $O (log n)$ in $O (log n)$ time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to ... $^{}$
Towards robust and efficient computation in dynamic peer-to-peer networks
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node ...

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 the author(s) 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

Funding Sources

Engineering and Physical Sciences Research Council
Singapore MOE
City University of Hong Kong

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

5
Total Citations
View Citations
199
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mertzios GMichail OSkretas GSpirakis PTheofilatos M(2024)The complexity of growing a graphJournal of Computer and System Sciences10.1016/j.jcss.2024.103587(103587)Online publication date: Sep-2024
https://doi.org/10.1016/j.jcss.2024.103587
Götte THinnenthal KScheideler CWerthmann J(2023)Time-optimal construction of overlay networksDistributed Computing10.1007/s00446-023-00442-436:3(313-347)Online publication date: 15-Feb-2023
https://doi.org/10.1007/s00446-023-00442-4
Mertzios GMichail OSkretas GSpirakis PTheofilatos M(2022)The Complexity of Growing a GraphAlgorithmics of Wireless Networks10.1007/978-3-031-22050-0_9(123-137)Online publication date: 13-Dec-2022
https://doi.org/10.1007/978-3-031-22050-0_9
Götte THinnenthal KScheideler CWerthmann JMiller ACensor-Hillel K(2021)Time-Optimal Construction of Overlay NetworksProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467932(457-468)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467932
Berns A(2021)Network Scaffolding for Efficient Stabilization of the Chord Overlay NetworkStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-91081-5_17(258-272)Online publication date: 17-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-91081-5_17
Berns A(2021)Applications and Implications of a General Framework for Self-Stabilizing Overlay NetworksStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-91081-5_16(243-257)Online publication date: 17-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-91081-5_16

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