{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:41:46Z","timestamp":1740134506100,"version":"3.37.3"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T00:00:00Z","timestamp":1401667200000},"content-version":"vor","delay-in-days":32,"URL":"http:\/\/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"],"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":"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 \n We first prove an individual lower bound of \u03a9(\n k<\/jats:italic>\n ) process steps for deterministic renaming into any namespace of size subexponential in\n k<\/jats:italic>\n , where\n 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 k<\/jats:italic>\n log (\n k<\/jats:italic>\n \/\n c<\/jats:italic>\n )) on the total step complexity of renaming into a namespace of size\n ck<\/jats:italic>\n , for any\n 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 \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 O<\/jats:italic>\n (log\n k<\/jats:italic>\n ), where\n 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":16,"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\/pdf\/10.1145\/2597630","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T20:51:15Z","timestamp":1672433475000},"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"}}]}}