{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T17:01:50Z","timestamp":1792947710706,"version":"4.5.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662486528","type":"print"},{"value":"9783662486535","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48653-5_19","type":"book-chapter","created":{"date-parts":[[2015,10,2]],"date-time":"2015-10-02T22:46:01Z","timestamp":1443825961000},"page":"276-291","source":"Crossref","is-referenced-by-count":16,"title":["Fast Byzantine Leader Election in Dynamic Networks"],"prefix":"10.1007","author":[{"given":"John","family":"Augustine","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,11,5]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Afek, Y., Awerbuch, B., Gafni, E.: Applying static network protocols to dynamic networks. In: FOCS 1987, pp. 358\u2013370 (1987)","DOI":"10.1109\/SFCS.1987.7"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Afek, Y., Gafni, E., Rosen, A.: The slide mechanism with applications in dynamic networks. In: ACM PODC, pp. 35\u201346 (1992)","DOI":"10.1145\/135419.135430"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Augustine, J., Molla, A.R., Morsy, E., Pandurangan, G., Robinson, P., Upfal, E.: Storage and search in dynamic peer-to-peer networks. In: SPAA, pp. 53\u201362 (2013)","DOI":"10.1145\/2486159.2486170"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Augustine, J., Pandurangan, G., Robinson, P.: Fast byzantine agreement in dynamic networks. In: PODC, pp. 74\u201383 (2013)","DOI":"10.1145\/2484239.2484275"},{"key":"19_CR5","unstructured":"Augustine, J., Pandurangan, G., Robinson, P., Roche, S., Upfal, E.: Enabling efficient and robust distributed computation in highly dynamic networks. In: FOCS (to appear, 2015)"},{"key":"19_CR6","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: SODA, pp. 551\u2013569 (2012)","DOI":"10.1137\/1.9781611973099.47"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-540-70575-8_11","volume-title":"Automata, Languages and Programming","author":"C Avin","year":"2008","unstructured":"Avin, C., Kouck\u00fd, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 121\u2013132. Springer, Heidelberg (2008)"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Patt-Shamir, B., Peleg, D., Saks, M.E.: Adapting to asynchronous dynamic networks. In: STOC 1992, pp. 557\u2013570 (1992)","DOI":"10.1145\/129712.129767"},{"issue":"6","key":"19_CR9","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1007\/s00224-006-1349-0","volume":"39","author":"A Bagchi","year":"2006","unstructured":"Bagchi, A., Bhargava, A., Chaudhary, A., Eppstein, D., Scheideler, C.: The effect of faults on network expansion. Theory Comput. Syst. 39(6), 903\u2013928 (2006)","journal-title":"Theory Comput. Syst."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. CoRR, abs\/1012.0009 (2010). Short version in ADHOC-NOW 2011","DOI":"10.1007\/978-3-642-22450-8_27"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/978-3-642-33651-5_10","volume-title":"Distributed Computing","author":"A Das Sarma","year":"2012","unstructured":"Das Sarma, A., Molla, A.R., Pandurangan, G.: Fast distributed computation in dynamic networks via random walks. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 136\u2013150. Springer, Heidelberg (2012)"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, B., Goldberg, L.A., Minder, L., Sauerwald, T., Scheideler, C.: Stabilizing consensus with the power of two choices. In: SPAA, pp. 149\u2013158 (2011)","DOI":"10.1145\/1989493.1989516"},{"key":"19_CR13","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6156.001.0001","volume-title":"Self-stabilization","author":"S Dolev","year":"2000","unstructured":"Dolev, S.: Self-stabilization. MIT Press, Cambridge (2000)"},{"issue":"5","key":"19_CR14","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1137\/0217061","volume":"17","author":"C Dwork","year":"1988","unstructured":"Dwork, C., Peleg, D., Pippenger, N., Upfal, E.: Fault tolerance in networks of bounded degree. SIAM J. Comput. 17(5), 975\u2013988 (1988)","journal-title":"SIAM J. Comput."},{"key":"19_CR15","unstructured":"Fiat, A., Saia, J.: Censorship resistant peer-to-peer content addressable networks. In: SODA, pp. 94\u2013103 (2002)"},{"issue":"1","key":"19_CR16","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1109\/TCOM.1981.1094876","volume":"29","author":"E Gafni","year":"1981","unstructured":"Gafni, E., Bertsekas, B.: Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Trans. Comm. 29(1), 11\u201318 (1981)","journal-title":"IEEE Trans. Comm."},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Huc, F., Kermarrec, A.-M.: Highly dynamic distributed computing with byzantine failures. In: PODC, pp. 176\u2013183 (2013)","DOI":"10.1145\/2484239.2484263"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-540-39989-6_23","volume-title":"Distributed Computing","author":"K Hildrum","year":"2003","unstructured":"Hildrum, K., Kubiatowicz, J.D.: Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks. In: Fich, F.E. (ed.) DISC 2003. LNCS, vol. 2848, pp. 321\u2013336. Springer, Heidelberg (2003)"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Kapron, B.M., Kempe, D., King, V., Saia, J., Sanwalani, V.: Fast asynchronous byzantine agreement and leader election with full information. ACM Transactions on Algorithms 6(4) (2010)","DOI":"10.1145\/1824777.1824788"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: Breaking the O(n $$^{2}$$ ) bit barrier: scalable Byzantine agreement with an adaptive adversary. In: PODC, pp. 420\u2013429 (2010)","DOI":"10.1145\/1835698.1835798"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: Faster agreement via a spectral method for detecting malicious behavior. In: SODA, pp. 785\u2013800 (2014)","DOI":"10.1137\/1.9781611973402.58"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA, pp. 990\u2013999 (2006)","DOI":"10.1145\/1109557.1109667"},{"key":"19_CR23","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":"19_CR24","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: ACM STOC, pp. 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Oshman, R., Moses, Y.: Coordinated consensus in dynamic networks. In: PODC, pp. 1\u201310 (2011)","DOI":"10.1145\/1993806.1993808"},{"key":"19_CR26","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 2003, vol. 3, pp. 2133\u20132143. IEEE Societies, March\u2013April 2003","DOI":"10.1109\/INFCOM.2003.1209234"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Naor, M., Wieder, U.: A simple fault tolerant distributed hash table. In: IPTPS, pp. 88\u201397 (2003)","DOI":"10.1007\/978-3-540-45172-3_8"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: DIALM-POMC, pp. 104\u2013110 (2005)","DOI":"10.1145\/1080810.1080828"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Raghavan, P., Upfal, E.: Building low-diameter p2p networks. In: FOCS, pp. 492\u2013499 (2001)","DOI":"10.1109\/SFCS.2001.959925"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Scheideler, C.: How to spread adversarial nodes?: rotate! In: STOC, pp. 704\u2013713 (2005)","DOI":"10.1145\/1060590.1060694"},{"issue":"2","key":"19_CR31","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1006\/inco.1994.1099","volume":"115","author":"E Upfal","year":"1994","unstructured":"Upfal, E.: Tolerating a linear number of faults in networks of bounded degree. Inf. Comput. 115(2), 312\u2013320 (1994)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48653-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T22:19:28Z","timestamp":1748643568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48653-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662486528","9783662486535"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48653-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}