{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T08:21:37Z","timestamp":1770538897545,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642157622","type":"print"},{"value":"9783642157639","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15763-9_9","type":"book-chapter","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T09:48:44Z","timestamp":1282643324000},"page":"94-108","source":"Crossref","is-referenced-by-count":15,"title":["Fast Randomized Test-and-Set and Renaming"],"prefix":"10.1007","author":[{"given":"Dan","family":"Alistarh","sequence":"first","affiliation":[]},{"given":"Hagit","family":"Attiya","sequence":"additional","affiliation":[]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[]},{"given":"Andrei","family":"Giurgiu","sequence":"additional","affiliation":[]},{"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s004460050039","volume":"11","author":"J.H. Anderson","year":"1997","unstructured":"Anderson, J.H., Moir, M.: Using local-spin k-exclusion algorithms to improve wait-free object implementations. Distrib. Comput.\u00a011(1), 1\u201320 (1997)","journal-title":"Distrib. Comput."},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BFb0020430","volume-title":"Distributed Algorithms","author":"M. Moir","year":"1994","unstructured":"Moir, M., Anderson, J.H.: Fast, long-lived renaming (extended abstract). In: Tel, G., Vit\u00e1nyi, P.M.B. (eds.) WDAG 1994. LNCS, vol.\u00a0857, pp. 141\u2013155. Springer, Heidelberg (1994)"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/3-540-61769-8_19","volume-title":"WDAG \u201996: Proceedings of the 10th International Workshop on Distributed Algorithms","author":"M. Moir","year":"1996","unstructured":"Moir, M., Garay, J.A.: Fast, long-lived renaming improved and simplified. In: Babao\u011flu, \u00d6., Marzullo, K. (eds.) WDAG 1996. LNCS, vol.\u00a01151, pp. 287\u2013303. Springer, Heidelberg (1996)"},{"issue":"2","key":"9_CR4","first-page":"858","volume":"46","author":"M. Herlihy","year":"1999","unstructured":"Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J.\u00a0ACM\u00a046(2), 858\u2013923 (1999)","journal-title":"J.\u00a0ACM"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1145\/1400751.1400791","volume-title":"PODC \u201908: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing","author":"A. Casta\u00f1eda","year":"2008","unstructured":"Casta\u00f1eda, A., Rajsbaum, S.: New combinatorial topology upper and lower bounds for renaming. In: PODC \u201908: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, pp. 295\u2013304. ACM, New York (2008)"},{"issue":"3","key":"9_CR6","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1145\/79147.79158","volume":"37","author":"H. Attiya","year":"1990","unstructured":"Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. Journal of the ACM\u00a037(3), 524\u2013548 (1990)","journal-title":"Journal of the ACM"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1145\/301308.301338","volume-title":"PODC \u201999: Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing","author":"Y. Afek","year":"1999","unstructured":"Afek, Y., Merritt, M.: Fast, wait-free (2k-1)-renaming. In: PODC \u201999: Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 105\u2013112. ACM, New York (1999)"},{"key":"9_CR8","first-page":"374","volume":"32","author":"M.J. Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J.\u00a0ACM\u00a032, 374\u2013382 (1985)","journal-title":"J.\u00a0ACM"},{"issue":"5","key":"9_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1411509.1411510","volume":"55","author":"H. Attiya","year":"2008","unstructured":"Attiya, H., Censor, K.: Tight bounds for asynchronous randomized consensus. J. ACM\u00a055(5), 1\u201326 (2008)","journal-title":"J. ACM"},{"issue":"3","key":"9_CR10","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00446-005-0143-6","volume":"18","author":"H. Attiya","year":"2006","unstructured":"Attiya, H., Kuhn, F., Plaxton, C.G., Wattenhofer, M., Wattenhofer, R.: Efficient adaptive collect using randomization. Distrib. Comput.\u00a018(3), 179\u2013188 (2006)","journal-title":"Distrib. Comput."},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.M.B.: Wait-free test-and-set (extended abstract). In: Segall, A., Zaks, S. (eds.) WDAG 1992. LNCS, vol.\u00a0647, pp. 85\u201394. Springer, Heidelberg (1992)"},{"key":"9_CR12","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":"9_CR13","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1145\/1400751.1400801","volume-title":"PODC \u201908: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing","author":"B.S. Chlebus","year":"2008","unstructured":"Chlebus, B.S., Kowalski, D.R.: Asynchronous exclusive selection. In: PODC \u201908: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, pp. 375\u2013384. ACM, New York (2008)"},{"key":"9_CR14","unstructured":"Alistarh, D., Attiya, H., Giurgiu, A., Gilbert, S., Guerraoui, R.: Fast randomized test-and-set and renaming, \n                    \n                      https:\/\/infoscience.epfl.ch\/record\/149943"},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/3-540-40026-5_2","volume-title":"Distributed Computing","author":"J.H. Anderson","year":"2000","unstructured":"Anderson, J.H., Kim, Y.-J.: Adaptive mutual exclusion with local spinning. In: Herlihy, M.P. (ed.) DISC 2000. LNCS, vol.\u00a01914, pp. 29\u201343. Springer, Heidelberg (2000)"},{"issue":"3","key":"9_CR16","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. Distrib. Comput.\u00a015(3), 127\u2013135 (2002)","journal-title":"Distrib. Comput."},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1145\/72981.72991","volume-title":"PODC \u201989: Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing","author":"J.E. Burns","year":"1989","unstructured":"Burns, J.E., Peterson, G.L.: The ambiguity of choosing. In: PODC \u201989: Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, pp. 145\u2013157. ACM, New York (1989)"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/164051.164056","volume-title":"PODC \u201993: Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing","author":"E. Borowsky","year":"1993","unstructured":"Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. In: PODC \u201993: Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, pp. 41\u201351. ACM, New York (1993)"},{"issue":"2","key":"9_CR19","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1137\/S0097539700366000","volume":"31","author":"H. Attiya","year":"2001","unstructured":"Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput.\u00a031(2), 642\u2013664 (2001)","journal-title":"SIAM J. Comput."},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/11864219_29","volume-title":"Distributed Computing","author":"A. Brodsky","year":"2006","unstructured":"Brodsky, A., Ellen, F., Woelfel, P.: Fully-adaptive algorithms for long-lived renaming. In: Dolev, S. (ed.) DISC 2006. LNCS, vol.\u00a04167, pp. 413\u2013427. Springer, Heidelberg (2006)"},{"issue":"3","key":"9_CR21","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.M.B.: Randomized naming using wait-free shared variables. Distributed Computing\u00a011(3), 113\u2013124 (1998)","journal-title":"Distributed Computing"},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1145\/114005.102808","volume":"13","author":"M. Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Trans. Programming Languages and Systems\u00a013, 123\u2013149 (1991)","journal-title":"ACM Trans. Programming Languages and Systems"},{"issue":"3","key":"9_CR23","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M. Herlihy","year":"1990","unstructured":"Herlihy, M., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst.\u00a012(3), 463\u2013492 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"5","key":"9_CR24","doi-asserted-by":"publisher","first-page":"1024","DOI":"10.1137\/S0097539792240881","volume":"25","author":"J. Aspnes","year":"1996","unstructured":"Aspnes, J., Waarts, O.: Randomized consensus in expected o(n\n                  log\n                  2\n                  n) operations per processor. SIAM J. Comput.\u00a025(5), 1024\u20131044 (1996)","journal-title":"SIAM J. Comput."},{"key":"9_CR25","doi-asserted-by":"crossref","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)"},{"key":"9_CR26","doi-asserted-by":"crossref","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)"},{"key":"9_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/3-540-45414-4_11","volume-title":"Distributed Computing","author":"C. Georgiou","year":"2001","unstructured":"Georgiou, C., Russell, A., Shvartsman, A.A.: The complexity of synchronous iterative do-all with crashes. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol.\u00a02180, pp. 151\u2013165. Springer, Heidelberg (2001)"},{"key":"9_CR28","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1145\/1007912.1007964","volume-title":"SPAA \u201904: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"D.R. Kowalski","year":"2004","unstructured":"Kowalski, D.R., Shvartsman, A.A.: Writing-all deterministically and optimally using a non-trivial number of asynchronous processors. In: SPAA \u201904: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 311\u2013320. ACM, New York (2004)"},{"key":"9_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-69045-2","volume-title":"Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity","author":"C. Georgiou","year":"2008","unstructured":"Georgiou, C., Shvartsman, A.A.: Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15763-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:21:45Z","timestamp":1558300905000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15763-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157622","9783642157639"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15763-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}