{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:06Z","timestamp":1740109326772,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:00:00Z","timestamp":1669248000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:00:00Z","timestamp":1669248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s00453-022-01068-x","type":"journal-article","created":{"date-parts":[[2022,11,25]],"date-time":"2022-11-25T13:05:36Z","timestamp":1669381536000},"page":"1029-1066","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Leader Election in Well-Connected Graphs"],"prefix":"10.1007","volume":"85","author":[{"given":"Seth","family":"Gilbert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6923-5762","authenticated-orcid":false,"given":"Suman","family":"Sourav","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,24]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Afek, Y., Gafni, E.: Time and message bounds for election in synchronous and asynchronous complete networks. In: Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC \u201985, pp. 186\u2013195, New York, NY, USA. ACM (1985)","key":"1068_CR1","DOI":"10.1145\/323596.323613"},{"doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors (extended abstract). In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC \u201980, pp. 82\u201393, New York, NY, USA. ACM (1980)","key":"1068_CR2","DOI":"10.1145\/800141.804655"},{"issue":"1","key":"1068_CR3","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF01553900","volume":"4","author":"H Attiya","year":"1989","unstructured":"Attiya, H., van Leeuwen, J., Santoro, N., Zaks, S.: Efficient elections in chordal ring networks. Algorithmica 4(1), 437\u2013446 (1989)","journal-title":"Algorithmica"},{"key":"1068_CR4","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley, New York (2004)","edition":"2"},{"doi-asserted-by":"crossref","unstructured":"Augustine, J., Pandurangan, G., Robinson, P.: Fast byzantine leader election in dynamic networks. In: Distributed Computing\u201429th International Symposium, DISC 2015, Tokyo, Japan, Oct 7\u20139, 2015, Proceedings, pp. 276\u2013291 (2015)","key":"1068_CR5","DOI":"10.1007\/978-3-662-48653-5_19"},{"doi-asserted-by":"crossref","unstructured":"Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC \u201987, pp. 230\u2013240, New York, NY, USA. ACM (1987)","key":"1068_CR6","DOI":"10.1145\/28395.28421"},{"issue":"3","key":"1068_CR7","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0195-6698(88)80014-3","volume":"9","author":"B Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B.: The isoperimetric number of random regular graphs. Eur. J. Comb. 9(3), 241\u2013244 (1988)","journal-title":"Eur. J. Comb."},{"key":"1068_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs. Cambridge Studies in Advanced Mathematics","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2001)"},{"issue":"4","key":"1068_CR9","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s004460050017","volume":"9","author":"J Brunekreef","year":"1996","unstructured":"Brunekreef, J., Katoen, J.-P., Koymans, R., Mauw, S.: Design and analysis of dynamic leader election protocols in broadcast networks. Distrib. Comput. 9(4), 157 (1996)","journal-title":"Distrib. Comput."},{"issue":"5","key":"1068_CR10","doi-asserted-by":"publisher","first-page":"1901","DOI":"10.1007\/s00453-018-0517-3","volume":"81","author":"A Casteigts","year":"2019","unstructured":"Casteigts, A., M\u00e9tivier, Y., Robson, J.M., Zemmari, A.: Deterministic leader election takes $$\\theta (d+\\log n)$$ bit rounds. Algorithmica 81(5), 1901\u20131920 (2019)","journal-title":"Algorithmica"},{"issue":"5","key":"1068_CR11","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1145\/359104.359108","volume":"22","author":"E Chang","year":"1979","unstructured":"Chang, E., Roberts, R.: An improved algorithm for decentralized extrema-finding in circular configurations of processes. Commun. ACM 22(5), 281\u2013283 (1979)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"Chatterjee, S., Pandurangan, G., Robinson, P.: The complexity of leader election: a chasm at diameter two. In: Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN \u201918, pp. 13:1\u201313:10, New York, NY, USA. ACM (2018)","key":"1068_CR12","DOI":"10.1145\/3154273.3154308"},{"issue":"1","key":"1068_CR13","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/s00453-018-0444-3","volume":"81","author":"Y Dieudonn\u00e9","year":"2019","unstructured":"Dieudonn\u00e9, Y., Pelc, A.: Impact of knowledge on election time in anonymous networks. Algorithmica 81(1), 238\u2013288 (2019)","journal-title":"Algorithmica"},{"issue":"5","key":"1068_CR14","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1109\/32.815321","volume":"25","author":"C Fetzer","year":"1999","unstructured":"Fetzer, C., Cristian, F.: A highly available local leader election service. IEEE Trans. Softw. Eng. 25(5), 603\u2013618 (1999)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"1","key":"1068_CR15","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1006\/jpdc.1996.0026","volume":"33","author":"P Flocchini","year":"1996","unstructured":"Flocchini, P., Mans, B.: Optimal elections in labeled hypercubes. J. Parallel Distrib. Comput. 33(1), 76\u201383 (1996)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"1","key":"1068_CR16","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1145\/7531.7919","volume":"34","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N., Lynch, N.A.: Electing a leader in a synchronous ring. J. ACM 34(1), 98\u2013115 (1987)","journal-title":"J. ACM"},{"issue":"4","key":"1068_CR17","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s00446-014-0237-0","volume":"28","author":"EG Fusco","year":"2015","unstructured":"Fusco, E.G., Pelc, A.: Knowledge, level of symmetry, and time of leader election. Distrib. Comput. 28(4), 221\u2013232 (2015)","journal-title":"Distrib. Comput."},{"issue":"1","key":"1068_CR18","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."},{"unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), Mar\u00a010\u201312, pp. 57\u201368 (2011)","key":"1068_CR19"},{"doi-asserted-by":"crossref","unstructured":"Gilbert, S., Kowalski, D.R.: Distributed agreement with optimal communication complexity. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201910, pp. 965\u2013977, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics (2010)","key":"1068_CR20","DOI":"10.1137\/1.9781611973075.78"},{"doi-asserted-by":"crossref","unstructured":"Gilbert, S., Robinson, P., Sourav, S.: Leader election in well-connected graphs. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC \u201918, pp. 227\u2013236, New York, NY, USA. Association for Computing Machinery (2018)","key":"1068_CR21","DOI":"10.1145\/3212734.3212754"},{"doi-asserted-by":"crossref","unstructured":"Gupta, I., van Renesse, R., Birman, K.P.: A probabilistically correct leader election protocol for large groups. In: Herlihy, M. (eds.) Distributed Computing, pp. 89\u2013103, Berlin. Springer, Berlin (2000)","key":"1068_CR22","DOI":"10.1007\/3-540-40026-5_6"},{"issue":"04","key":"1068_CR23","doi-asserted-by":"publisher","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. Am. Math. Soc. 43(04), 439\u2013562 (2006)","journal-title":"Bull. Am. Math. Soc."},{"doi-asserted-by":"crossref","unstructured":"Jerrum, M., Sinclair, A.: Conductance and the rapid mixing property for markov chains: the approximation of permanent resolved. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC \u201988, pp. 235\u2013244, New York, NY, USA. ACM (1988)","key":"1068_CR24","DOI":"10.1145\/62212.62234"},{"unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS \u201900, p. 565, Washington, DC, USA. IEEE Computer Society (2000)","key":"1068_CR25"},{"issue":"2","key":"1068_CR26","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":"7","key":"1068_CR27","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1016\/j.jcss.2013.04.003","volume":"79","author":"DR Kowalski","year":"2013","unstructured":"Kowalski, D.R., Pelc, A.: Leader election in ad hoc radio networks: a keen ear helps. J. Comput. Syst. Sci. 79(7), 1164\u20131180 (2013)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1068_CR28","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-7:27 (2015)","journal-title":"J. ACM"},{"issue":"PB","key":"1068_CR29","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(PB), 134\u2013143 (2015)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Le Lann, G.: Distributed systems: towards a formal approach. In: IFIP Congress, pp. 155\u2013160 (1977)","key":"1068_CR30"},{"key":"1068_CR31","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996)"},{"issue":"2","key":"1068_CR32","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1006\/inco.2001.3054","volume":"170","author":"D Malkhi","year":"2001","unstructured":"Malkhi, D., Reiter, M.K., Wool, A., Wright, R.N.: Probabilistic quorum systems. Inf. Comput. 170(2), 184\u2013206 (2001)","journal-title":"Inf. Comput."},{"key":"1068_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)"},{"doi-asserted-by":"crossref","unstructured":"Molla, A.R., Pandurangan, G.: Distributed computation of mixing time. In: Proceedings of the 18th International Conference on Distributed Computing and Networking, ICDCN \u201917, pp. 5:1\u20135:4, New York, NY, USA. ACM (2017)","key":"1068_CR34","DOI":"10.1145\/3007748.3007784"},{"key":"1068_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"doi-asserted-by":"crossref","unstructured":"Newport, C.: Leader election in a smartphone peer-to-peer network. In: 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 172\u2013181 (2017)","key":"1068_CR36","DOI":"10.1109\/IPDPS.2017.11"},{"issue":"2","key":"1068_CR37","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/BF02526036","volume":"18","author":"M Overmars","year":"1997","unstructured":"Overmars, M., Santoro, N.: Improved bounds for electing a leader in a synchronous ring. Algorithmica 18(2), 246\u2013262 (1997)","journal-title":"Algorithmica"},{"key":"1068_CR38","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. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"issue":"1","key":"1068_CR39","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0743-7315(90)90074-Y","volume":"8","author":"D Peleg","year":"1990","unstructured":"Peleg, D.: Time-optimal leader election in general networks. J. Parallel Distrib. Comput. 8(1), 96\u201399 (1990)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"2","key":"1068_CR40","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/s10959-013-0497-9","volume":"28","author":"Y Peres","year":"2015","unstructured":"Peres, Y., Sousi, P.: Mixing times are hitting times of large sets. J. Theor. Probab. 28(2), 488\u2013519 (2015)","journal-title":"J. Theor. Probab."},{"issue":"5","key":"1068_CR41","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s00446-007-0022-4","volume":"19","author":"MK Ramanathan","year":"2007","unstructured":"Ramanathan, M.K., Ferreira, R.A., Jagannathan, S., Grama, A., Szpankowski, W.: Randomized leader election. Distrib. Comput. 19(5), 403\u2013418 (2007)","journal-title":"Distrib. Comput."},{"issue":"4","key":"1068_CR42","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1145\/964723.383072","volume":"31","author":"S Ratnasamy","year":"2001","unstructured":"Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. SIGCOMM Comput. Commun. Rev. 31(4), 161\u2013172 (2001)","journal-title":"SIGCOMM Comput. Commun. Rev."},{"doi-asserted-by":"crossref","unstructured":"Rowstron, A.I.T., Druschel, P.: Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Proceedings of the IFIP\/ACM International Conference on Distributed Systems Platforms Heidelberg, Middleware \u201901, pp. 329\u2013350, London, UK. Springer (2001)","key":"1068_CR43","DOI":"10.1007\/3-540-45518-3_18"},{"key":"1068_CR44","volume-title":"Algorithms for Random Generation and Counting","author":"A Sinclair","year":"1993","unstructured":"Sinclair, A.: Algorithms for Random Generation and Counting. Birkhauser, Boston (1993)"},{"issue":"3","key":"1068_CR45","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1109\/71.491576","volume":"7","author":"G Singh","year":"1996","unstructured":"Singh, G.: Leader election in the presence of link failures. IEEE Trans. Parallel Distrib. Syst. 7(3), 231\u2013236 (1996)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"unstructured":"Sourav, S.: Latency, conductance, and the role of connectivity in graph problems. https:\/\/scholarbank.nus.edu.sg\/handle\/10635\/162756 (2019)","key":"1068_CR46"},{"issue":"1","key":"1068_CR47","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1109\/JSAC.2003.818784","volume":"22","author":"BY Zhao","year":"2006","unstructured":"Zhao, B.Y., Huang, L., Stribling, J., Rhea, S.C., Joseph, A.D., Kubiatowicz, J.D.: Tapestry: a resilient global-scale overlay for service deployment. IEEE J. Sel. A. Commun. 22(1), 41\u201353 (2006)","journal-title":"IEEE J. Sel. A. Commun."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01068-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01068-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01068-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,29]],"date-time":"2023-03-29T13:13:32Z","timestamp":1680095612000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01068-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,24]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1068"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01068-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,11,24]]},"assertion":[{"value":"23 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}