{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:32:31Z","timestamp":1750307551042,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"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":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>\n            A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented once by each of\n            <jats:italic>n<\/jats:italic>\n            processes in a model that allows up to\n            <jats:italic>n<\/jats:italic>\n            -1 crash failures. For any fixed \u03f5, the counter achieves a relative error of \u03b4 with high probability, at the cost of\n            <jats:italic>O<\/jats:italic>\n            (((1\/\u03b4) log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1\/\u03f5)\n            <\/jats:sup>\n            ) register operations per increment and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/5+\u03f5<\/jats:sup>\n            ((1\/\u03b4) log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1\/\u03f5)\n            <\/jats:sup>\n            ) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first counter implementation that is sublinear the number of processes and works despite a strong adversary scheduler that can observe internal states of processes.\n          <\/jats:p>\n          <jats:p>\n            An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) to an optimal\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ), resolving one of the last remaining open problems concerning consensus in this model.\n          <\/jats:p>","DOI":"10.1145\/1721837.1721841","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Approximate shared-memory counting despite a strong adversary"],"prefix":"10.1145","volume":"6","author":[{"given":"James","family":"Aspnes","sequence":"first","affiliation":[{"name":"Yale University, New Haven, CT"}]},{"given":"Keren","family":"Censor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2010,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/62546.62594"},{"key":"e_1_2_1_2_1","unstructured":"Alon N. and Spencer J. H. 1992. The Probabilistic Method. John Wiley &amp; Sons.  Alon N. and Spencer J. H. 1992. The Probabilistic Method. John Wiley &amp; Sons."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1022"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278304"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400794"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90021-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240881"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250814"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146427"},{"volume":"579","volume-title":"Proceedings of the 5th International Workshop on Distributed Algorithms. S. Toueg, P. G. Spirakis, and L. M. Kirousis, Eds. Lecture Notes in Computer Science","author":"Bracha G.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.47"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934993"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_15_1","unstructured":"Grimmet G. R. and Stirzaker D. R. 1992. Probability and Random Processes 2nd Ed. Oxford Science Publications.  Grimmet G. R. and Stirzaker D. R. 1992. Probability and Random Processes 2nd Ed. Oxford Science Publications."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.38"},{"key":"e_1_2_1_17_1","unstructured":"Hall P. and Heyde C. 1980. Martingale Limit Theory and Its Application. Academic Press.  Hall P. and Heyde C. 1980. Martingale Limit Theory and Its Application. Academic Press."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_21_1","unstructured":"Loui M. C. and Abu-Amara H. H. 1987. Memory requirements for agreement among unreliable asynchronous processes. Advan. Comput. Res. 163--183.  Loui M. C. and Abu-Amara H. H. 1987. Memory requirements for agreement among unreliable asynchronous processes. Advan. Comput. Res. 163--183."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.   Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"volume-title":"Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 351--362","author":"Saks M.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","unstructured":"Wormald N. C. 1999. The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms M. Karonski and H. J. Proemel Eds. 73--155.  Wormald N. C. 1999. The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms M. Karonski and H. J. Proemel Eds. 73--155."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721841","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721837.1721841","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:38Z","timestamp":1750249418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721841"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721837.1721841"],"URL":"https:\/\/doi.org\/10.1145\/1721837.1721841","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}