{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:00:52Z","timestamp":1743058852633,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030643478"},{"type":"electronic","value":"9783030643485"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-64348-5_14","type":"book-chapter","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T07:04:38Z","timestamp":1606201478000},"page":"183-198","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Smoothed Analysis of Leader Election in Distributed Networks"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1537-3462","authenticated-orcid":false,"given":"Anisur Rahaman","family":"Molla","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4556-0071","authenticated-orcid":false,"given":"Disha","family":"Shur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,25]]},"reference":[{"issue":"2","key":"14_CR1","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1137\/0220023","volume":"20","author":"Y Afek","year":"1991","unstructured":"Afek, Y., Gafni, E.: Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J. Comput. 20(2), 376\u2013394 (1991)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"14_CR2","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1038\/scientificamerican0302-40","volume":"286","author":"DP Anderson","year":"2002","unstructured":"Anderson, D.P., Kubiatowicz, J.: Introduction to distributed algorithms. The worldwide computer. Sci. Am. 286(3), 28\u201335 (2002)","journal-title":"Sci. Am."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Angel, O., Bubeck, S., Peres, Y., Wei, F.: Local max-cut in smoothed polynomial time. In: STOC (2017)","DOI":"10.1145\/3055399.3055402"},{"issue":"5","key":"14_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2027216.2027217","volume":"58","author":"D Arthur","year":"2011","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: Smoothed analysis of the k-means method. J. ACM 58(5), 1\u201331 (2011)","journal-title":"J. ACM"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Augustine, J., Molla, A.R., Pandurangan, G.: Sublinear message bounds for randomized agreement. In: PODC, pp. 315\u2013324. ACM (2018)","DOI":"10.1145\/3212734.3212751"},{"key":"14_CR6","doi-asserted-by":"publisher","unstructured":"Blum, A., Hopcroft, J., Kannan, R.: Foundations of Data Science. Cambridge University Press (2020). https:\/\/doi.org\/10.1017\/9781108755528","DOI":"10.1017\/9781108755528"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Chatterjee, S., Pandurangan, G., Pham, N.D.: Distributed MST: a smoothed analysis. In: ICDCN, pp. 15:1\u201315:10 (2020)","DOI":"10.1145\/3369740.3369778"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-662-48653-5_34","volume-title":"Distributed Computing","author":"M Dinitz","year":"2015","unstructured":"Dinitz, M., Fineman, J., Gilbert, S., Newport, C.: Smoothed analysis of dynamic networks. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 513\u2013527. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48653-5_34"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-22006-7_15","volume-title":"Automata, Languages and Programming","author":"R Els\u00e4sser","year":"2011","unstructured":"Els\u00e4sser, R., Tscheuschner, T.: Settling the complexity of local max-cut (almost) completely. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 171\u2013182. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22006-7_15"},{"issue":"2","key":"14_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3011870","volume":"13","author":"M Etscheid","year":"2017","unstructured":"Etscheid, M., R\u00f6glin, H.: Smoothed analysis of local search for the maximum-cut problem. ACM Trans. Algorithms 13(2), 1\u201312 (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"14_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"RG Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Gilbert, S., Robinson, P., Sourav, S.: Leader election in well-connected graphs. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 227\u2013236 (2018)","DOI":"10.1145\/3212734.3212754"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Humblet, P.: Electing a leader in a clique in o(n log n) messages. Intern. Memo., Laboratory for Information and Decision Systems. M.I.T., Cambridge, MA (1984)","DOI":"10.21236\/ADA146581"},{"key":"14_CR14","doi-asserted-by":"publisher","unstructured":"Kadjouh, N., et al.: A dominating tree based leader election algorithm for smart cities IoT infrastructure. Mob. Netw. Appl., 1\u201314 (2020). https:\/\/doi.org\/10.1007\/s11036-020-01599-z","DOI":"10.1007\/s11036-020-01599-z"},{"issue":"3","key":"14_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00446-012-0157-9","volume":"25","author":"M Khan","year":"2012","unstructured":"Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., Talwar, K.: Efficient distributed approximation algorithms via probabilistic tree embeddings. Distrib. Comput. 25(3), 189\u2013205 (2012). https:\/\/doi.org\/10.1007\/s00446-012-0157-9","journal-title":"Distrib. Comput."},{"issue":"1","key":"14_CR16","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/77606.77610","volume":"12","author":"E Korach","year":"1990","unstructured":"Korach, E., Kutten, S., Moran, S.: A modular technique for the design of efficient distributed leader finding algorithms. ACM Trans. Program. Lang. Syst. 12(1), 84\u2013101 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"14_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/0216019","volume":"16","author":"E Korach","year":"1987","unstructured":"Korach, E., Moran, S., Zaks, S.: The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM J. Comput. 16(2), 231\u2013236 (1987)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"14_CR18","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(89)90103-5","volume":"64","author":"E Korach","year":"1989","unstructured":"Korach, E., Moran, S., Zaks, S.: Optimal lower bounds for some distributed algorithms for a complete network of processors. Theor. Comput. Sci. 64(1), 125\u2013132 (1989)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"14_CR19","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/2699440","volume":"62","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM 62(1), 7:1\u20137:27 (2015)","journal-title":"J. ACM"},{"key":"14_CR20","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2014.02.009","volume":"561","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Sublinear bounds for randomized leader election. Theor. Comput. Sci. 561, 134\u2013143 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-15763-9_45","volume-title":"Distributed Computing","author":"S Kutten","year":"2010","unstructured":"Kutten, S., Zinenko, D.: Low communication self-stabilization through randomization. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 465\u2013479. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15763-9_45"},{"key":"14_CR22","unstructured":"Lann, G.L.: Distributed systems - towards a formal approach. In: Information Processing, Proceedings of the 7th IFIP Congress 1977, pp. 155\u2013160 (1977)"},{"key":"14_CR23","volume-title":"Markov Chains and Mixing Times","author":"DA Levin","year":"2006","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2006)"},{"key":"14_CR24","unstructured":"Pandurangan, G.: Distributed network algorithms (2018). http:\/\/sites.google.com\/site\/gopalpandurangan\/dnabook.pdf"},{"key":"14_CR25","doi-asserted-by":"publisher","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":"14_CR26","unstructured":"Rahman, M.U.: Leader election in the Internet of Things: challenges and opportunities. CoRR abs\/1911.00759 (2019). http:\/\/arxiv.org\/abs\/1911.00759"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Ratnasamy, S., Francis, P., Handley, M., Karp, R.M., Shenker, S.: A scalable content-addressable network. In: SIGCOMM, pp. 161\u2013172. ACM (2001)","DOI":"10.1145\/964723.383072"},{"issue":"3","key":"14_CR28","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/3232535","volume":"62","author":"T Roughgarden","year":"2019","unstructured":"Roughgarden, T.: Beyond worst-case analysis. Commun. ACM 62(3), 88\u201396 (2019)","journal-title":"Commun. ACM"},{"issue":"6","key":"14_CR29","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1109\/MWC.2004.1368895","volume":"11","author":"E Shi","year":"2004","unstructured":"Shi, E., Perrig, A.: Designing secure sensor networks. IEEE Wirel. Commun. 11(6), 38\u201343 (2004)","journal-title":"IEEE Wirel. Commun."},{"key":"14_CR30","unstructured":"Singh, G.: Efficient distributed algorithms for leader election in complete networks. In: ICDCS, pp. 472\u2013479. IEEE Computer Society (1991)"},{"issue":"3","key":"14_CR31","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"7","key":"14_CR32","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1538788.1538794","volume":"52","author":"A Wright","year":"2009","unstructured":"Wright, A.: Contemporary approaches to fault tolerance. Commun. ACM 52(7), 13\u201315 (2009)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-64348-5_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T09:03:22Z","timestamp":1606208602000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-64348-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030643478","9783030643485"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-64348-5_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 November 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SSS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Stabilizing, Safety, and Security of Distributed Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 November 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 November 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.cse.msu.edu\/~sandeep\/SSS2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}