{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T16:40:02Z","timestamp":1745944802353,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642356674"},{"type":"electronic","value":"9783642356681"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-35668-1_24","type":"book-chapter","created":{"date-parts":[[2013,1,4]],"date-time":"2013-01-04T10:07:03Z","timestamp":1357294023000},"page":"348-362","source":"Crossref","is-referenced-by-count":14,"title":["Sublinear Bounds for Randomized Leader Election"],"prefix":"10.1007","author":[{"given":"Shay","family":"Kutten","sequence":"first","affiliation":[]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[]},{"given":"Amitabh","family":"Trehan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"24_CR1","doi-asserted-by":"crossref","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. SICOMP\u00a020(2), 376\u2013394 (1991)","journal-title":"SICOMP"},{"issue":"2","key":"24_CR2","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1006\/inco.1994.1075","volume":"113","author":"Y. Afek","year":"1994","unstructured":"Afek, Y., Matias, Y.: Elections in anonymous networks. Inf. Comput.\u00a0113(2), 312\u2013330 (1994)","journal-title":"Inf. Comput."},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors (extended abstract). In: STOC, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Augustine, J., Pandurangan, G., Robinson, P., Upfal, E.: Towards robust and efficient distributed computation in dynamic peer-to-peer networks. In: SODA (2012)","DOI":"10.1137\/1.9781611973099.47"},{"issue":"1","key":"24_CR5","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/inco.1994.1065","volume":"113","author":"M. Snir","year":"1994","unstructured":"Snir, M., Scheiber, B.: Calling names on nameless networks. Inf. Comput.\u00a0113(1), 80\u2013101 (1994)","journal-title":"Inf. Comput."},{"issue":"4","key":"24_CR6","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(86)90025-6","volume":"22","author":"M.C. Loui","year":"1986","unstructured":"Loui, M.C., Matsushita, T.A., West, D.B.: Election in a complete network with a sense of direction. Information Processing Letters\u00a022(4), 185\u2013187 (1986)","journal-title":"Information Processing Letters"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Chandra, T.D., Griesemer, R., Redstone, J.: Paxos made live - an engineering perspective (2006 invited talk). In: Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (2007)","DOI":"10.1145\/1281100.1281103"},{"issue":"1","key":"24_CR8","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R.G. 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.\u00a05(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-40026-5_6","volume-title":"Distributed Computing","author":"I. Gupta","year":"2000","unstructured":"Gupta, I., van Renesse, R., Birman, K.P.: A Probabilistically Correct Leader Election Protocol for Large Groups. In: Herlihy, M.P. (ed.) DISC 2000. LNCS, vol.\u00a01914, pp. 89\u2013103. Springer, Heidelberg (2000)"},{"key":"24_CR10","volume-title":"Electing a leader in a clique in O(n logn) messages. Intern. Memo., Laboratory for Information and Decision Systems","author":"P. Humblet","year":"1984","unstructured":"Humblet, P.: Electing a leader in a clique in O(n logn) messages. Intern. Memo., Laboratory for Information and Decision Systems. M.I.T, Cambridge (1984)"},{"issue":"1","key":"24_CR11","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/0890-5401(90)90004-2","volume":"88","author":"A. Itai","year":"1990","unstructured":"Itai, A., Rodeh, M.: Symmetry breaking in distributed networks. Inf. Comput.\u00a088(1), 60\u201387 (1990)","journal-title":"Inf. Comput."},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1145\/1400751.1400787","volume-title":"Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, PODC 2008","author":"M. Khan","year":"2008","unstructured":"Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., Talwar, K.: Efficient distributed approximation algorithms via probabilistic tree embeddings. In: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, PODC 2008, pp. 263\u2013272. ACM, New York (2008)"},{"issue":"1","key":"24_CR13","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.\u00a012(1), 84\u2013101 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"24_CR14","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1145\/800222.806747","volume-title":"PODC 1984","author":"E. Korach","year":"1984","unstructured":"Korach, E., Moran, S., Zaks, S.: Tight lower and upper bounds for some distributed algorithms for a complete network of processors. In: PODC 1984, pp. 199\u2013207. ACM, New York (1984)"},{"issue":"2","key":"24_CR15","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 Journal on Computing\u00a016(2), 231\u2013236 (1987)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"24_CR16","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. Theoretical Computer Science\u00a064(1), 125\u2013132 (1989)","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"24_CR17","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/359545.359563","volume":"21","author":"L. Lamport","year":"1978","unstructured":"Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM\u00a021(7), 558\u2013565 (1978)","journal-title":"Commun. ACM"},{"issue":"2","key":"24_CR18","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1145\/279227.279229","volume":"16","author":"L. Lamport","year":"1998","unstructured":"Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst.\u00a016(2), 133\u2013169 (1998)","journal-title":"ACM Trans. Comput. Syst."},{"key":"24_CR19","unstructured":"Le Lann, G.: Distributed systems - towards a formal approach. In: IFIP Congress, pp. 155\u2013160 (1977)"},{"key":"24_CR20","volume-title":"Distributed Algorithms","author":"N. Lynch","year":"1996","unstructured":"Lynch, N.: Distributed Algorithms. Morgan Kaufman Publishers, Inc., San Francisco (1996)"},{"key":"24_CR21","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/259380.259458","volume-title":"PODC 1997","author":"D. Malkhi","year":"1997","unstructured":"Malkhi, D., Reiter, M., Wright, R.: Probabilistic quorum systems. In: PODC 1997, pp. 267\u2013273. ACM, New York (1997)"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2004)","DOI":"10.1017\/CBO9780511813603"},{"issue":"3","key":"24_CR23","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1842733.1842736","volume":"44","author":"E. Nygren","year":"2010","unstructured":"Nygren, E., Sitaraman, R.K., Sun, J.: The akamai network: a platform for high-performance internet applications. SIGOPS Oper. Syst. Rev.\u00a044(3), 2\u201319 (2010)","journal-title":"SIGOPS Oper. Syst. Rev."},{"issue":"1","key":"24_CR24","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. Journal of Parallel and Distributed Computing\u00a08(1), 96\u201399 (1990)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"24_CR25","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Ramanathan, M.K., Ferreira, R.A., Jagannathan, S., Grama, A., Szpankowski, W.: Randomized leader election. Distributed Computing, 403\u2013418 (2007)","DOI":"10.1007\/s00446-007-0022-4"},{"key":"24_CR27","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1145\/383059.383072","volume-title":"SIGCOMM 2001","author":"S. Ratnasamy","year":"2001","unstructured":"Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. In: SIGCOMM 2001, pp. 161\u2013172. ACM, New York (2001)"},{"key":"24_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/3-540-45518-3_18","volume-title":"Middleware 2001","author":"A. Rowstron","year":"2001","unstructured":"Rowstron, A., Druschel, P.: Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. In: Guerraoui, R. (ed.) Middleware 2001. LNCS, vol.\u00a02218, pp. 329\u2013350. Springer, Heidelberg (2001)"},{"key":"24_CR29","doi-asserted-by":"crossref","unstructured":"Santoro, N.: Design and Analysis of Distributed Algorithms. Wiley Series on Parallel and Distributed Computing. Wiley-Interscience (2006)","DOI":"10.1002\/0470072644"},{"key":"24_CR30","doi-asserted-by":"crossref","unstructured":"Singh, G.: Efficient distributed algorithms for leader election in complete networks. In: ICDCS, pp. 472\u2013479 (1991)","DOI":"10.1109\/ICDCS.1991.148712"},{"key":"24_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0020419","volume-title":"Introduction to distributed algorithms","author":"G. Tel","year":"1994","unstructured":"Tel, G.: Introduction to distributed algorithms. Cambridge University Press, New York (1994)"},{"issue":"1","key":"24_CR32","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1109\/JSAC.2003.818784","volume":"22","author":"B.Y. Zhao","year":"2004","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 Journal on Selected Areas in Communications\u00a022(1), 41\u201353 (2004)","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"24_CR33","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\u00a0Communication Self-stabilization through Randomization. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol.\u00a06343, pp. 465\u2013479. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing and Networking"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35668-1_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T16:00:12Z","timestamp":1745942412000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35668-1_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642356674","9783642356681"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35668-1_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}