{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:25Z","timestamp":1750220665865,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T00:00:00Z","timestamp":1596153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Engineering and Physical Sciences Research Council","award":["EP\/P021247\/1 (COSHER)"],"award-info":[{"award-number":["EP\/P021247\/1 (COSHER)"]}]},{"name":"Singapore MOE","award":["MOE2018-T2-1-160"],"award-info":[{"award-number":["MOE2018-T2-1-160"]}]},{"name":"City University of Hong Kong","award":["Project No. 7200639\/CS"],"award-info":[{"award-number":["Project No. 7200639\/CS"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,31]]},"DOI":"10.1145\/3382734.3405716","type":"proceedings-article","created":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T22:33:55Z","timestamp":1596234835000},"page":"438-447","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead"],"prefix":"10.1145","author":[{"given":"Seth","family":"Gilbert","sequence":"first","affiliation":[{"name":"National University of Singapore"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"University of Houston"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[{"name":"City University of Hong Kong"}]},{"given":"Amitabh","family":"Trehan","sequence":"additional","affiliation":[{"name":"Loughborough University"}]}],"member":"320","published-online":{"date-parts":[[2020,7,31]]},"reference":[{"volume-title":"Fast Construction of Overlay Networks. In SPAA","year":"2005","author":"Angluin Dana","key":"e_1_3_2_1_1_1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290674"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290674"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902945.2902959"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"J Augustine G Pandurangan P Robinson and E Upfal. 2012. Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks. In SODA.  J Augustine G Pandurangan P Robinson and E Upfal. 2012. Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks. In SODA.","DOI":"10.1137\/1.9781611973099.47"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9099-9"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"S Baswana and S Sen. 2003. A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n1+1\/k) Size in Weighted Graphs. In ICALP. 384--296.  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.","DOI":"10.1007\/3-540-45061-0_32"},{"volume-title":"International Conference on 0","year":"2009","author":"Berns A","key":"e_1_3_2_1_9_1"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.02.021"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2833312.2833328"},{"volume-title":"Handley","year":"2009","author":"Cooper Colin","key":"e_1_3_2_1_12_1"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"A. Das Sarma A. Molla and G. Pandurangan. 2012. Fast Distributed Computation in Dynamic Networks via Random Walks. In DISC.  A. Das Sarma A. Molla and G. Pandurangan. 2012. Fast Distributed Computation in Dynamic Networks via Random Walks. In DISC.","DOI":"10.1007\/978-3-642-33651-5_10"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Atish Das Sarma Danupon Nanongkai and Gopal Pandurangan. 2009. Fast distributed random walks. In PODC. 161--170.  Atish Das Sarma Danupon Nanongkai and Gopal Pandurangan. 2009. Fast distributed random walks. In PODC. 161--170.","DOI":"10.1145\/1582716.1582745"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Michael Elkin. 2007. A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In PODC. 185--194.  Michael Elkin. 2007. A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In PODC. 185--194.","DOI":"10.1145\/1281100.1281128"},{"volume-title":"DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead. to appear on arXiv","year":"2020","author":"Gilbert Seth","key":"e_1_3_2_1_16_1"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1016\/j.peva.2005.01.002"},{"volume-title":"PODC '08","author":"Hayes T","key":"e_1_3_2_1_18_1"},{"volume-title":"The Forgiving Graph: a distributed data structure for low stretch under adversarial attack. Distributed Computing","year":"2012","author":"Hayes T","key":"e_1_3_2_1_19_1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629695"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Valerie King Jared Saia Vishal Sanwalani and Erik Vee. 2006. Towards Secure and Scalable Computation in Peer-to-Peer Networks. In FOCS. 87--98.  Valerie King Jared Saia Vishal Sanwalani and Erik Vee. 2006. Towards Secure and Scalable Computation in Peer-to-Peer Networks. In FOCS. 87--98.","DOI":"10.1109\/FOCS.2006.77"},{"key":"e_1_3_2_1_23_1","unstructured":"Sebastian Kniesburges Andreas Koutsopoulos and Christian Scheideler. [n.d.]. Re-Chord: a self-stabilizing chord overlay network (SPAA '11). 235--244.  Sebastian Kniesburges Andreas Koutsopoulos and Christian Scheideler. [n.d.]. Re-Chord: a self-stabilizing chord overlay network (SPAA '11). 235--244."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Fabian Kuhn Stefan Schmid and Roger Wattenhofer. 2005. A Self-repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn. In IPTPS. 13--23.  Fabian Kuhn Stefan Schmid and Roger Wattenhofer. 2005. A Self-repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn. In IPTPS. 13--23.","DOI":"10.1007\/11558989_2"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0099-z"},{"volume-title":"Distributed Computing.","author":"Kutten Shay","key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0056467"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2003.1209234"},{"volume-title":"Markov chains and mixing times","author":"Levin D A","key":"e_1_3_2_1_28_1"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0346-0332-4"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_31_1","unstructured":"N. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann.  N. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.07.011"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273350"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Gopal Pandurangan Prabhakar Raghavan and Eli Upfal. 2001. Building Low-Diameter P2P Networks. In FOCS. 492--499.  Gopal Pandurangan Prabhakar Raghavan and Eli Upfal. 2001. Building Low-Diameter P2P Networks. In FOCS. 492--499.","DOI":"10.1109\/SFCS.2001.959925"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-015-0258-3"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0192-1"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/964723.383072"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.2307\/3062153"},{"key":"e_1_3_2_1_40_1","unstructured":"M.K. Reiter A. Samar and C. Wang. 2005. Distributed construction of a fault-tolerant network from a tree. In SRDS. 155 -- 165.  M.K. Reiter A. Samar and C. Wang. 2005. Distributed construction of a fault-tolerant network from a tree. In SRDS. 155 -- 165."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45518-3_18"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Jared Saia and Amitabh Trehan. 2008. Picking up the Pieces: Self-Healing in reconfigurable networks. In IPDPS.  Jared Saia and Amitabh Trehan. 2008. Picking up the Pieces: Self-Healing in reconfigurable networks. In IPDPS.","DOI":"10.1109\/IPDPS.2008.4536326"},{"key":"e_1_3_2_1_43_1","article-title":"Distributed Random Walks","volume":"60","author":"Sarma Atish Das","year":"2013","journal-title":"J. ACM"},{"volume-title":"Workshop on Network Science for Communication Networks (NetSciCom","year":"2012","author":"Sarma Atish Das","key":"e_1_3_2_1_44_1"},{"key":"e_1_3_2_1_45_1","article-title":"M\u00e9moire sur le nombre de valeurs que peut prendre une fonction quand on permute les lettres qu'elle renferme","author":"Serret J-A","year":"1850","journal-title":"Journal de math\u00e9matiques pures et appliqu\u00e9es (1850), 1--44."},{"volume-title":"Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications. ACM SIGCOMM Conference","year":"2001","author":"Stoica I.","key":"e_1_3_2_1_46_1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.808407"},{"volume-title":"Algorithms for self-healing networks. Dissertation","author":"Trehan Amitabh","key":"e_1_3_2_1_48_1"},{"volume-title":"Self-healing using virtual structures. CoRR abs\/1202.2466","year":"2012","author":"Trehan A","key":"e_1_3_2_1_49_1"},{"key":"e_1_3_2_1_50_1","first-page":"41","article-title":"Tapestry: a resilient global-scale overlay for service deployment. Selected Areas in Communications","volume":"22","author":"Zhao B.Y.","year":"2004","journal-title":"IEEE Journal on"}],"event":{"name":"PODC '20: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '20"},"container-title":["Proceedings of the 39th Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3405716","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382734.3405716","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:49Z","timestamp":1750197769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3405716"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,31]]},"references-count":50,"alternative-id":["10.1145\/3382734.3405716","10.1145\/3382734"],"URL":"https:\/\/doi.org\/10.1145\/3382734.3405716","relation":{},"subject":[],"published":{"date-parts":[[2020,7,31]]},"assertion":[{"value":"2020-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}