{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T22:12:36Z","timestamp":1767046356536,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,5,1]],"date-time":"2014-05-01T00:00:00Z","timestamp":1398902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0916389"],"award-info":[{"award-number":["CCF-0916389"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace.<\/jats:p>\n          <jats:p>\n            We first prove an individual lower bound of \u03a9(\n            <jats:italic>k<\/jats:italic>\n            ) process steps for deterministic renaming into any namespace of size subexponential in\n            <jats:italic>k<\/jats:italic>\n            , where\n            <jats:italic>k<\/jats:italic>\n            is the number of participants. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues, and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of \u03a9(\n            <jats:italic>k<\/jats:italic>\n            log (\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>c<\/jats:italic>\n            )) on the total step complexity of renaming into a namespace of size\n            <jats:italic>ck<\/jats:italic>\n            , for any\n            <jats:italic>c<\/jats:italic>\n            \u2265 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors.\n          <\/jats:p>\n          <jats:p>\n            On the algorithmic side, we give a protocol that transforms any sorting network into a randomized strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>k<\/jats:italic>\n            ), where\n            <jats:italic>k<\/jats:italic>\n            is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost.\n          <\/jats:p>","DOI":"10.1145\/2597630","type":"journal-article","created":{"date-parts":[[2014,5,27]],"date-time":"2014-05-27T12:56:59Z","timestamp":1401195419000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Tight Bounds for Asynchronous Renaming"],"prefix":"10.1145","volume":"61","author":[{"given":"Dan","family":"Alistarh","sequence":"first","affiliation":[{"name":"Microsoft Research Cambridge, Cambridge, UK"}]},{"given":"James","family":"Aspnes","sequence":"additional","affiliation":[{"name":"Yale, New Haven, CT"}]},{"given":"Keren","family":"Censor-Hillel","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2014,6,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153741"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301335"},{"volume-title":"Vit\u00e1nyi","year":"1992","author":"Afek Yehuda","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301338"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808726"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2075029.2075039"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993850"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.66"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888781.1888794"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31104-8_17"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050039"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2108242.2108244"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332507"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.185815"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79158"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460100068"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2001.1730"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366000"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.60"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374410"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242714"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0143-6"},{"volume-title":"Distributed Computing. Fundamentals, Simulations, and Advanced Topics","author":"Attiya Hagit","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/72981.73003"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.84"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/164051.164056"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_29"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/72981.72991"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0108-2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2108242.2108245"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00242-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400801"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215006"},{"edition":"3","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/365559.365617"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/645955.675812"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01783662"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.47"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536428"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993687"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281105"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784242"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277735"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317299"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0152-6"},{"edition":"2","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth Donald E.","key":"e_1_2_1_49_1"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1110"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/7351.7352"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90103-5"},{"key":"e_1_2_1_53_1","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan-Kaufmann.   Nancy A. Lynch. 1996. Distributed Algorithms. Morgan-Kaufmann."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(95)00009-H"},{"volume-title":"Garay","year":"1996","author":"Moir Mark","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.001"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050045"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460200071"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2597630","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2597630","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:58Z","timestamp":1750234198000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2597630"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":59,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1145\/2597630"],"URL":"https:\/\/doi.org\/10.1145\/2597630","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}