{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T07:18:53Z","timestamp":1778743133926,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2008,10,1]],"date-time":"2008-10-01T00:00:00Z","timestamp":1222819200000},"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p>\n            A distributed consensus algorithm allows\n            <jats:italic>n<\/jats:italic>\n            processes to reach a common decision value starting from individual inputs.\n            <jats:italic>Wait-free<\/jats:italic>\n            consensus, in which a process always terminates within a finite number of its own steps, is impossible in an asynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminate with probability 1. Randomized consensus algorithms are typically evaluated by their\n            <jats:italic>total step complexity<\/jats:italic>\n            , which is the expected total number of steps taken by all processes.\n          <\/jats:p>\n          <jats:p>\n            This article proves that the total step complexity of randomized consensus is \u0398(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) in an asynchronous shared memory system using multi-writer multi-reader registers. This result is achieved by improving both the lower and the upper bounds for this problem.\n          <\/jats:p>\n          <jats:p>\n            In addition to improving upon the best previously known result by a factor of log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            , the lower bound features a greatly streamlined proof. Both goals are achieved through restricting attention to a set of\n            <jats:italic>layered<\/jats:italic>\n            executions and using an isoperimetric inequality for analyzing their behavior.\n          <\/jats:p>\n          <jats:p>\n            The matching algorithm decreases the expected total step complexity by a log\n            <jats:italic>n<\/jats:italic>\n            factor, by leveraging the multi-writing capability of the shared registers. Its correctness proof is facilitated by viewing each execution of the algorithm as a stochastic process and applying Kolmogorov's inequality.\n          <\/jats:p>","DOI":"10.1145\/1411509.1411510","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T13:49:43Z","timestamp":1225979383000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":50,"title":["Tight bounds for asynchronous randomized consensus"],"prefix":"10.1145","volume":"55","author":[{"given":"Hagit","family":"Attiya","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keren","family":"Censor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/62546.62594"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Alon N. and Spencer J. H. 2000. The Probabilistic Method 2nd ed. Wiley New York.  Alon N. and Spencer J. H. 2000. The Probabilistic Method 2nd ed. Wiley New York.","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93433"},{"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.1007\/s00446-002-0081-5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400794"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90021-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240881"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400793"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/72981.73001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/983102"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259441"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-004-0113-4"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Aumann Y."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277733"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132543"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 5th International Workshop on Distributed Algorithms (WDAG). Springer-Verlag, Berlin\/Heidelberg, Germany, 143--150","author":"Bracha G."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/248052.248083"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41848"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212045"},{"key":"e_1_2_1_21_1","unstructured":"Feller W. 1968. An Introduction to Probability Theory and Its Applications 3rd ed. Vol. 1. Wiley New York.  Feller W. 1968. An Introduction to Probability Theory and Its Applications 3rd ed. Vol. 1. Wiley New York."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.30"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Kapron B."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109667"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.77"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_30_1","unstructured":"Loui M. C. and Abu-Amara H. H. 1987. Memory Requirements for Agreement Among Unreliable Asynchronous Processes. JAI Press Greenwich Conn. 163--183.  Loui M. C. and Abu-Amara H. H. 1987. Memory Requirements for Agreement Among Unreliable Asynchronous Processes. JAI Press Greenwich Conn. 163--183."},{"key":"e_1_2_1_31_1","unstructured":"Lynch N. A. 1996. Distributed Algorithms. Morgan-Kaufmann San Mateo CA.   Lynch N. A. 1996. Distributed Algorithms. Morgan-Kaufmann San Mateo CA."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364006"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambrigde University Press Cambridge UK.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambrigde University Press Cambridge UK.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/PRDC.2005.10"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Saks M."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Springer-Verlag, Berlin\/Heidelberg, Germany 304--313","author":"Santoro N."},{"key":"e_1_2_1_37_1","volume-title":"Lecture Notes in Mathematics: Martingle Theory in Harmonic Analysis and Banach Spaces.","author":"Schechtman G."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/98163.98167"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1411509.1411510","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1411509.1411510","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:29Z","timestamp":1750253369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1411509.1411510"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1145\/1411509.1411510"],"URL":"https:\/\/doi.org\/10.1145\/1411509.1411510","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10]]},"assertion":[{"value":"2007-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}