{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:13:10Z","timestamp":1765231990353,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,2,1]],"date-time":"2012-02-01T00:00:00Z","timestamp":1328054400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["953\/06"],"award-info":[{"award-number":["953\/06"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0435201"],"award-info":[{"award-number":["CNS-0435201"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>\n            This article presents constructions of useful concurrent data structures, including max registers and counters, with step complexity that is sublinear in the number of processes,\n            <jats:italic>n<\/jats:italic>\n            . This result avoids a well-known lower bound by having step complexity that is polylogarithmic in the number of values the object can take or the number of operations applied to it.\n          <\/jats:p>\n          <jats:p>\n            The key step in these implementations is a method for constructing a\n            <jats:italic>max register<\/jats:italic>\n            , a linearizable, wait-free concurrent data structure that supports a write operation and a read operation that returns the largest value previously written. For fixed\n            <jats:italic>m<\/jats:italic>\n            , an\n            <jats:italic>m<\/jats:italic>\n            -valued max register is constructed from one-bit multi-writer multi-reader registers at a cost of at most \u2308log\n            <jats:italic>m<\/jats:italic>\n            \u2309 atomic register operations per write or read. An\n            <jats:italic>unbounded<\/jats:italic>\n            max register is constructed with cost\n            <jats:italic>O<\/jats:italic>\n            (min(log\n            <jats:italic>v<\/jats:italic>\n            ,\n            <jats:italic>n<\/jats:italic>\n            )) to read or write a value\n            <jats:italic>v<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Max registers are used to transform any monotone circuit into a wait-free concurrent data structure that provides write operations setting the inputs to the circuit and a read operation that returns the value of the circuit on the largest input values previously supplied. One application is a simple, linearizable, wait-free counter with a cost of\n            <jats:italic>O<\/jats:italic>\n            (min(log\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>v<\/jats:italic>\n            ,\n            <jats:italic>n<\/jats:italic>\n            )) to perform an increment and\n            <jats:italic>O<\/jats:italic>\n            (min(log\n            <jats:italic>v<\/jats:italic>\n            ,\n            <jats:italic>n<\/jats:italic>\n            )) to perform a read, where\n            <jats:italic>v<\/jats:italic>\n            is the current value of the counter. For polynomially-many increments, this becomes\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), an exponential improvement on the best previously known upper bounds of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) for exact counting and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/5+\u03f5<\/jats:sup>\n            ) for approximate counting.\n          <\/jats:p>\n          <jats:p>\n            Finally, it is shown that the upper bounds are almost optimal. It is shown that for deterministic implementations, even if they are only required to satisfy solo-termination, min(\u2308log\n            <jats:italic>m<\/jats:italic>\n            \u2309,\n            <jats:italic>n<\/jats:italic>\n            -1) is a lower bound on the worst-case complexity for an\n            <jats:italic>m<\/jats:italic>\n            -valued bounded max register, which is exactly equal to the upper bound for\n            <jats:italic>m<\/jats:italic>\n            \u2264 2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n              -1\n            <\/jats:sup>\n            , and min(\n            <jats:italic>n<\/jats:italic>\n            -1, \u2308 log\n            <jats:italic>m<\/jats:italic>\n            \u2309 - log(\u2308 log\n            <jats:italic>m<\/jats:italic>\n            \u2309 +\n            <jats:italic>k<\/jats:italic>\n            )) is a lower bound for the read operation of an\n            <jats:italic>m<\/jats:italic>\n            -valued\n            <jats:italic>k<\/jats:italic>\n            -additive-accurate counter, which is a bounded counter in which a read operation is allowed to return a value within an additive error of \u00b1\n            <jats:italic>k<\/jats:italic>\n            of the number of increment operations linearized before it. Furthermore, even in a solo-terminating randomized implementation of an\n            <jats:italic>n<\/jats:italic>\n            -valued max register with an oblivious adversary and global coins, there exist simple schedules in which, with high probability, the worst-case step complexity of a read operation is \u03a9(log\n            <jats:italic>n<\/jats:italic>\n            \/log log\n            <jats:italic>n<\/jats:italic>\n            ) if the write operations have polylogarithmic step complexity.\n          <\/jats:p>","DOI":"10.1145\/2108242.2108244","type":"journal-article","created":{"date-parts":[[2012,2,28]],"date-time":"2012-02-28T12:58:35Z","timestamp":1330433915000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Polylogarithmic concurrent data structures from monotone circuits"],"prefix":"10.1145","volume":"59","author":[{"given":"James","family":"Aspnes","sequence":"first","affiliation":[{"name":"Yale University, New Haven, CT"}]},{"given":"Hagit","family":"Attiya","sequence":"additional","affiliation":[{"name":"Technion, Israel"}]},{"given":"Keren","family":"Censor-Hillel","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA"}]}],"member":"320","published-online":{"date-parts":[[2012,3,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.1007\/BF02242703"},{"volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09)","author":"Aspnes J.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90021-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366000"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460100067"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90071-5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.47"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"volume":"857","volume-title":"Proceedings of the 8th International Workshop on Distributed Algorithms (WDAG'94)","author":"Inoue M.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185868"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571875"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317299"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2108242.2108244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2108242.2108244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:08Z","timestamp":1750241168000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2108242.2108244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1145\/2108242.2108244"],"URL":"https:\/\/doi.org\/10.1145\/2108242.2108244","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2012,2]]},"assertion":[{"value":"2010-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}