{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T04:21:06Z","timestamp":1770956466920,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,11,27]],"date-time":"2015-11-27T00:00:00Z","timestamp":1448582400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2016,6]]},"DOI":"10.1007\/s00446-015-0258-3","type":"journal-article","created":{"date-parts":[[2015,11,27]],"date-time":"2015-11-27T09:20:50Z","timestamp":1448616050000},"page":"163-185","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["DEX: self-healing expanders"],"prefix":"10.1007","volume":"29","author":[{"given":"Gopal","family":"Pandurangan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7442-7002","authenticated-orcid":false,"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[]},{"given":"Amitabh","family":"Trehan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,27]]},"reference":[{"key":"258_CR1","volume-title":"The Probabilistic Method","author":"N Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (1992)"},{"issue":"6","key":"258_CR2","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s00446-008-0071-3","volume":"21","author":"J Aspnes","year":"2009","unstructured":"Aspnes, J., Wieder, U.: The expansion and mixing time of skip graphs with applications. Distrib. Comput. 21(6), 385\u2013393 (2009)","journal-title":"Distrib. Comput."},{"key":"258_CR3","doi-asserted-by":"crossref","unstructured":"Augustine, J., Pandurangan, G., Robinson, P., Upfal, E.: Towards robust and efficient computation in dynamic peer-to-peer networks. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 551\u2013569 (2012)","DOI":"10.1137\/1.9781611973099.47"},{"key":"258_CR4","first-page":"123","volume":"17","author":"J Bertrand","year":"1845","unstructured":"Bertrand, J.: M\u00e9moire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu\u2019elle renferme. J. l\u2019Ecole Roy. Polytech. 17, 123\u2013140 (1845)","journal-title":"J. l\u2019Ecole Roy. Polytech."},{"key":"258_CR5","volume-title":"Spectral Graph Theory","author":"F Chung","year":"1997","unstructured":"Chung, F.: Spectral Graph Theory. AMS, Providence (1997)"},{"key":"258_CR6","doi-asserted-by":"crossref","unstructured":"Cooper, C., Dyer, M., Handley, A.J.: The flip markov chain and a randomising p2p protocol. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC), pp. 141\u2013150 (2009)","DOI":"10.1145\/1582716.1582742"},{"key":"258_CR7","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Nanongkai, D., Pandurangan, G.: Fast distributed random walks. In: PODC, pp. 161\u2013170 (2009)","DOI":"10.1145\/1582716.1582745"},{"key":"258_CR8","doi-asserted-by":"crossref","unstructured":"Dolev, S., Tzachar, N.: Spanders: distributed spanning expanders. In: SAC, pp. 1309\u20131314 (2010)","DOI":"10.1145\/1774088.1774369"},{"issue":"4","key":"258_CR9","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1137\/S0097539794268765","volume":"27","author":"D Gillman","year":"1998","unstructured":"Gillman, D.: A Chernoff bound for random walks on expander graphs. SIAM J. Comput. 27(4), 1203\u20131220 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"258_CR10","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.peva.2005.01.002","volume":"63","author":"C Gkantsidis","year":"2006","unstructured":"Gkantsidis, C., Mihail, M., Saberi, A.: Random walks in peer-to-peer networks: algorithms and evaluation. Perform. Eval. 63(3), 241\u2013263 (2006)","journal-title":"Perform. Eval."},{"issue":"8","key":"258_CR11","doi-asserted-by":"crossref","first-page":"3830","DOI":"10.1137\/090769752","volume":"39","author":"M Gurevich","year":"2010","unstructured":"Gurevich, M., Keidar, I.: Correctness of gossip-based membership under message loss. SIAM J. Comput. 39(8), 3830\u20133859 (2010)","journal-title":"SIAM J. Comput."},{"key":"258_CR12","author":"T Hayes","year":"2012","unstructured":"Hayes, T., Saia, J., Trehan, A.: The forgiving graph: a distributed data structure for low stretch under adversarial attack. Distrib. Comput. (2012). doi: 10.1007\/s00446-012-0160-1","journal-title":"Distrib. Comput."},{"key":"258_CR13","doi-asserted-by":"crossref","unstructured":"Hayes, T., Rustagi, N., Saia, J., Trehan, A.: The forgiving tree: a self-healing distributed data structure. In: PODC \u201908: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, pp. 203\u2013212. New York, NY, USA (2008)","DOI":"10.1145\/1400751.1400779"},{"issue":"04","key":"258_CR14","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. AMS 43(04), 439\u2013562 (2006)","journal-title":"Bull. AMS"},{"issue":"6","key":"258_CR15","doi-asserted-by":"crossref","first-page":"36:1","DOI":"10.1145\/2629695","volume":"61","author":"R Jacob","year":"2014","unstructured":"Jacob, R., Richa, A., Scheideler, C., Schmid, S., T\u00e4ubig, H.: $$\\text{ SKIP }+$$ SKIP + : a self-stabilizing skip graph. J. ACM 61(6), 36:1\u201336:26 (2014)","journal-title":"J. ACM"},{"key":"258_CR16","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J., Sanwalani, V., Vee, E.: Towards secure and scalable computation in peer-to-peer networks. In: FOCS, pp. 87\u201398 (2006)","DOI":"10.1109\/FOCS.2006.77"},{"key":"258_CR17","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Schmid, S., Wattenhofer, R.: A self-repairing peer-to-peer system resilient to dynamic adversarial churn. In: 4th International Workshop on Peer-To-Peer Systems (IPTPS), Cornell University, Ithaca, New York, USA, Springer LNCS 3640, February 2005","DOI":"10.1007\/11558989_2"},{"key":"258_CR18","doi-asserted-by":"crossref","unstructured":"Law, C., Siu, K.-Y.: Distributed construction of random expander networks. In: Twenty-Second Annual Joint Conference of the IEEE Computer and Communications (INFOCOM), pp. 2133\u20132143 (2003)","DOI":"10.1109\/INFCOM.2003.1209234"},{"key":"258_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0346-0332-4","volume-title":"Discrete groups, expanding graphs and invariant measures, vol 125, Progress in Mathematics","author":"A Lubotzky","year":"1994","unstructured":"Lubotzky, A.: Discrete groups, expanding graphs and invariant measures, vol 125, Progress in Mathematics. Birkh\u00e4user, Basel (1994)"},{"issue":"12","key":"258_CR20","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1016\/j.jpdc.2008.07.011","volume":"68","author":"R Melamed","year":"2008","unstructured":"Melamed, R., Keidar, I.: Araneola: a scalable reliable multicast system for dynamic environments. J. Parallel Distrib. Comput. 68(12), 1539\u20131560 (2008)","journal-title":"J. Parallel Distrib. Comput."},{"key":"258_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)"},{"issue":"3","key":"258_CR22","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/1273340.1273350","volume":"3","author":"M Naor","year":"2007","unstructured":"Naor, M., Wieder, U.: Novel architectures for p2p applications: the continuous-discrete approach. ACM Trans. Algorithms 3(3), 34 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"258_CR23","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Raghavan, P., Upfal, E.: Building low-diameter P2P networks. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 492\u2013499 (2001)","DOI":"10.1109\/SFCS.2001.959925"},{"key":"258_CR24","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Trehan, A.: Xheal: localized self-healing using expanders. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. PODC \u201911, pp. 301\u2013310. ACM, New York, NY, USA (2011)","DOI":"10.1145\/1993806.1993865"},{"key":"258_CR25","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"258_CR26","doi-asserted-by":"crossref","unstructured":"Reiter, M., Samar, A., Wang, C.: Distributed construction of a fault-tolerant network from a tree. In: 24th IEEE Symposium on Reliable Distributed Systems (SRDS), pp. 155\u2013165 (2005)","DOI":"10.1109\/RELDIS.2005.16"},{"key":"258_CR27","doi-asserted-by":"crossref","unstructured":"Saia, J., Trehan, A.: Picking up the pieces: self-healing in reconfigurable networks. In: IPDPS. 22nd IEEE International Symposium on Parallel and Distributed Processing, pp. 1\u201312. IEEE, April 2008","DOI":"10.1109\/IPDPS.2008.4536326"},{"key":"258_CR28","doi-asserted-by":"crossref","unstructured":"Scheideler, C.: Universal Routing Strategies for Interconnection Networks, volume 1390 of Lecture Notes in Computer Science. Springer, Berlin (1998)","DOI":"10.1007\/BFb0052928"},{"key":"258_CR29","unstructured":"Trehan, A.: Algorithms for self-healing networks. Dissertation, University of New Mexico (2010)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0258-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-015-0258-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0258-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,1]],"date-time":"2019-09-01T20:46:50Z","timestamp":1567370810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-015-0258-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,27]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["258"],"URL":"https:\/\/doi.org\/10.1007\/s00446-015-0258-3","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,27]]}}}