{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:40Z","timestamp":1763468140882},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642415265"},{"type":"electronic","value":"9783642415272"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-41527-2_4","type":"book-chapter","created":{"date-parts":[[2013,10,3]],"date-time":"2013-10-03T10:55:48Z","timestamp":1380797748000},"page":"46-60","source":"Crossref","is-referenced-by-count":15,"title":["An $O(\\sqrt n)$ Space Bound for Obstruction-Free Leader Election"],"prefix":"10.1007","author":[{"given":"George","family":"Giakkoupis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maryam","family":"Helmi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lisa","family":"Higham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Woelfel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"4_CR1","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1145\/153724.153741","volume":"40","author":"Y. Afek","year":"1993","unstructured":"Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. of the ACM\u00a040(4), 873\u2013890 (1993)","journal-title":"J. of the ACM"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-56188-9_6","volume-title":"Distributed Algorithms","author":"Y. Afek","year":"1992","unstructured":"Afek, Y., Gafni, E., Tromp, J., Vit\u00e1nyi, P.: Wait-free test-and-set. In: Segall, A., Zaks, S. (eds.) WDAG 1992. LNCS, vol.\u00a0647, pp. 85\u201394. Springer, Heidelberg (1992)"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J.: Sub-logarithmic test-and-set against a weak adversary. In: Peleg, D. (ed.) DISC. LNCS, vol.\u00a06950, pp. 97\u2013109. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-24100-0_7"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., Censor-Hillel, K., Gilbert, S., Zadimoghaddam, M.: Optimal-time adaptive strong renaming, with applications to counting. In: Proc. of 30th PODC, pp. 239\u2013248 (2011)","DOI":"10.1145\/1993806.1993850"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., Gilbert, S., Guerraoui, R.: The complexity of renaming. In: Proc. of 52nd FOCS, pp. 718\u2013727 (2011)","DOI":"10.1109\/FOCS.2011.66"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-642-15763-9_9","volume-title":"Distributed Computing","author":"D. Alistarh","year":"2010","unstructured":"Alistarh, D., Attiya, H., Gilbert, S., Giurgiu, A., Guerraoui, R.: Fast randomized test-and-set and renaming. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol.\u00a06343, pp. 94\u2013108. Springer, Heidelberg (2010)"},{"issue":"3","key":"4_CR7","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02242703","volume":"6","author":"J.H. Anderson","year":"1993","unstructured":"Anderson, J.H.: Composite registers. Dist. Comp.\u00a06(3), 141\u2013154 (1993)","journal-title":"Dist. Comp."},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-642-24100-0_36","volume-title":"Distributed Computing","author":"J. Aspnes","year":"2011","unstructured":"Aspnes, J.: Randomized consensus in expected o(n\n                           2) total work using single-writer registers. In: Peleg, D. (ed.) DISC. LNCS, vol.\u00a06950, pp. 363\u2013373. Springer, Heidelberg (2011)"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Aspnes, J.: Faster randomized consensus with an oblivious adversary. In: Proc. of 31st PODC, pp. 1\u20138 (2012)","DOI":"10.1145\/2332432.2332434"},{"issue":"2","key":"4_CR10","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00446-011-0134-8","volume":"25","author":"J. Aspnes","year":"2012","unstructured":"Aspnes, J.: A modular approach to shared-memory consensus, with applications to the probabilistic-write model. Dist. Comp.\u00a025(2), 179\u2013188 (2012)","journal-title":"Dist. Comp."},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Attiya, H., Censor, K.: Tight bounds for asynchronous randomized consensus. J. of the ACM\u00a055(5) (2008)","DOI":"10.1145\/1411509.1411510"},{"issue":"8","key":"4_CR12","doi-asserted-by":"publisher","first-page":"3885","DOI":"10.1137\/090751906","volume":"39","author":"H. Attiya","year":"2010","unstructured":"Attiya, H., Censor-Hillel, K.: Lower bounds for randomized consensus under a weak adversary. SIAM J. on Comp.\u00a039(8), 3885\u20133904 (2010)","journal-title":"SIAM J. on Comp."},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Aumann, Y.: Efficient asynchronous consensus with the weak adversary scheduler. In: Proc. of 16th PODC, pp. 209\u2013218 (1997)","DOI":"10.1145\/259380.259441"},{"issue":"3","key":"4_CR14","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s00446-005-0121-z","volume":"18","author":"H. Buhrman","year":"2006","unstructured":"Buhrman, H., Panconesi, A., Silvestri, R., Vit\u00e1nyi, P.: On the importance of having an identity or, is consensus really universal? Dist. Comp.\u00a018(3), 167\u2013176 (2006)","journal-title":"Dist. Comp."},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BFb0056480","volume-title":"Distributed Computing","author":"W. Eberly","year":"1998","unstructured":"Eberly, W., Higham, L., Warpechowska-Gruca, J.: Long-lived, fast, waitfree renaming with optimal name space and high throughput. In: Kutten, S. (ed.) DISC 1998. LNCS, vol.\u00a01499, pp. 149\u2013160. Springer, Heidelberg (1998)"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Ellen, F., Fatourou, P., Ruppert, E.: Time lower bounds for implementations of multi-writer snapshots. J. of the ACM\u00a054(6) (2007)","DOI":"10.1145\/1314690.1314694"},{"issue":"2","key":"4_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s00446-008-0060-6","volume":"21","author":"F. Ellen","year":"2008","unstructured":"Ellen, F., Fatourou, P., Ruppert, E.: The space complexity of unbounded timestamps. Dist. Comp.\u00a021(2), 103\u2013115 (2008)","journal-title":"Dist. Comp."},{"issue":"5","key":"4_CR18","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/290179.290183","volume":"45","author":"F. Fich","year":"1998","unstructured":"Fich, F., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. J. of the ACM\u00a045(5), 843\u2013862 (1998)","journal-title":"J. of the ACM"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/11561927_8","volume-title":"Distributed Computing","author":"F.E. Fich","year":"2005","unstructured":"Fich, F.E., Luchangco, V., Moir, M., Shavit, N.N.: Obstruction-free algorithms can be practically wait-free. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.\u00a03724, pp. 78\u201392. Springer, Heidelberg (2005)"},{"issue":"2","key":"4_CR20","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"M. Fischer","year":"1985","unstructured":"Fischer, M., Lynch, N., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. of the ACM\u00a032(2), 374\u2013382 (1985)","journal-title":"J. of the ACM"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Woelfel, P.: On the time and space complexity of randomized test-and-set. In: Proc. of 31st PODC, pp. 19\u201328 (2012)","DOI":"10.1145\/2332432.2332436"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"2726","DOI":"10.1137\/070686445","volume":"39","author":"W. Golab","year":"2010","unstructured":"Golab, W., Hendler, D., Woelfel, P.: An O(1) RMRs leader election algorithm. SIAM J. on Comp.\u00a039, 2726\u20132760 (2010)","journal-title":"SIAM J. on Comp."},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Helmi, M., Higham, L., Pacheco, E., Woelfel, P.: The space complexity of long-lived and one-shot timestamp implementations. In: Proc. of 30th PODC, pp. 139\u2013148 (2011)","DOI":"10.1145\/1993806.1993826"},{"issue":"1","key":"4_CR24","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M. Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst.\u00a013(1), 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"4_CR25","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1137\/S0097539797317299","volume":"30","author":"P. Jayanti","year":"2000","unstructured":"Jayanti, P., Tan, K., Toueg, S.: Time and space lower bounds for nonblocking implementations. SIAM J. on Comp.\u00a030(2), 438\u2013456 (2000)","journal-title":"SIAM J. on Comp."},{"issue":"4","key":"4_CR26","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1145\/48022.48024","volume":"10","author":"C. Kruskal","year":"1988","unstructured":"Kruskal, C., Rudolph, L., Snir, M.: Efficient synchronization on multiprocessors with shared memory. ACM Trans. Program. Lang. Syst.\u00a010(4), 579\u2013601 (1988)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195\u2013248. Springer (1998)","DOI":"10.1007\/978-3-662-12788-9_6"},{"issue":"3","key":"4_CR28","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s004460050045","volume":"11","author":"A. Panconesi","year":"1998","unstructured":"Panconesi, A., Papatriantafilou, M., Tsigas, P., Vit\u00e1nyi, P.: Randomized naming using wait-free shared variables. Dist. Comp.\u00a011(3), 113\u2013124 (1998)","journal-title":"Dist. Comp."},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"Styer, E., Peterson, G.: Tight bounds for shared memory symmetric mutual exclusion problems. In: Proc. of 8th PODC, pp. 177\u2013191 (1989)","DOI":"10.1145\/72981.72993"},{"issue":"3","key":"4_CR30","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s004460200071","volume":"15","author":"J. Tromp","year":"2002","unstructured":"Tromp, J., Vit\u00e1nyi, P.: Randomized two-process wait-free test-and-set. Dist. Comp.\u00a015(3), 127\u2013135 (2002)","journal-title":"Dist. Comp."}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-41527-2_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T14:35:41Z","timestamp":1558103741000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-41527-2_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642415265","9783642415272"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-41527-2_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}