TY - GEN
T1 - DConstructor
T2 - 39th Symposium on Principles of Distributed Computing, PODC 2020
AU - Gilbert, Seth
AU - Pandurangan, Gopal
AU - Robinson, Peter
AU - Trehan, Amitabh
N1 - Funding Information:
∗Seth Gilbert was supported by Singapore grant MOE2018-T2-1-160. †Gopal Pandurangan was supported, in part, by NSF grants IIS-1633720, CCF-1717075, and CCF-1540512. ‡Peter Robinson was supported by a grant from City University of Hong Kong Project No. 7200639/CS. §Amitabh Trehan was supported by the Engineering and Physical Sciences Research Council (EPSRC) grant EP/P021247/1 (COSHER).
Publisher Copyright:
© 2020 ACM.
PY - 2020/7/31
Y1 - 2020/7/31
N2 - 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.
AB - 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.
KW - distributed protocol
KW - expander
KW - peer-to-peer network
KW - randomized algorithm
KW - self-repairing network
UR - http://www.scopus.com/inward/record.url?scp=85090355391&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090355391&partnerID=8YFLogxK
U2 - 10.1145/3382734.3405716
DO - 10.1145/3382734.3405716
M3 - Conference contribution
AN - SCOPUS:85090355391
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 438
EP - 447
BT - PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
Y2 - 3 August 2020 through 7 August 2020
ER -