{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:40:46Z","timestamp":1782970846262,"version":"3.54.5"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T00:00:00Z","timestamp":1660608000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>\n            Assuming that there is an\n            <jats:italic>a priori<\/jats:italic>\n            agreement between processes on the names of shared memory locations, as is done in almost all the publications on concurrent shared memory algorithms, is tantamount to assuming that agreement has already been solved at a lower level. It is intriguing to figure out how coordination can be achieved without relying on such lower-level agreement. To better understand the new model, we first design new algorithms for several important problems, such as mutual exclusion, consensus, election, and renaming. Then, we prove space lower bounds, impossibility results, and resolve two foundational long-standing open problems in the context of anonymous memory systems.\n          <\/jats:p>\n          <jats:p>Using these results, we identify fundamental differences between the standard shared memory model and the strictly weaker anonymous shared memory model. Besides enabling us to understand better the intrinsic limits for coordinating the actions of asynchronous processes, the new model has been shown to be useful in modeling biologically inspired distributed computing methods, especially those based on ideas from molecular biology.<\/jats:p>","DOI":"10.1145\/3529752","type":"journal-article","created":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T11:16:56Z","timestamp":1651663016000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Anonymous Shared Memory"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3070-5370","authenticated-orcid":false,"given":"Gadi","family":"Taubenfeld","sequence":"first","affiliation":[{"name":"Reichman University, Herzliya, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,8,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933116"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331594"},{"key":"e_1_3_2_4_2","volume-title":"Proceedings of the 12th ACM Symposium on Theory of Computing (STOC\u201980)","author":"Angluin D.","year":"1980","unstructured":"D. Angluin. 1980. Local and global properties in networks of processes. In Proceedings of the 12th ACM Symposium on Theory of Computing (STOC\u201980)."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0081-5"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79158"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/2684017"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792541"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3119"},{"key":"e_1_3_2_10_2","first-page":"307","volume-title":"Proceedings of the 8th ACM Symposium. on Principles of Distributed Computing","author":"Bar-Noy A.","year":"1989","unstructured":"A. Bar-Noy and D. Dolev. 1989. Shared memory versus message-passing in an asynchronous distributed environment. In Proceedings of the 8th ACM Symposium. on Principles of Distributed Computing. 307\u2013318."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0169-5"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167119"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0301-7"},{"key":"e_1_3_2_14_2","volume-title":"Obstruction-free snapshot, obstruction-free consensus, and fetch-and-add modulo k","author":"Bowman J.","year":"2011","unstructured":"J. Bowman. 2011. Obstruction-free snapshot, obstruction-free consensus, and fetch-and-add modulo k. Technical Report Technical Report TR2011-681. Dartmouth College."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0137-5"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0121-z"},{"key":"e_1_3_2_17_2","first-page":"833","volume-title":"Proceedings of the18th Annual Allerton Conference on Communication, Control and Computing","author":"Burns J. E.","year":"1980","unstructured":"J. E. Burns and N. A. Lynch. 1980. Mutual exclusion using indivisible reads and writes. In Proceedings of the18th Annual Allerton Conference on Communication, Control and Computing. 833\u2013842."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1065"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2011.04.001"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087822"},{"key":"e_1_3_2_21_2","series-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017)","first-page":"12:1\u201312:14","volume":"91","author":"Chan D. Y. C.","year":"2017","unstructured":"D. Y. C. Chan, V. Hadzilacos, and S. Toueg. 2017. On the number of objects with distinct power and the linearizability of set agreement objects. In Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017)(Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 91). 12:1\u201312:14."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212775"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198121"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1043"},{"key":"e_1_3_2_25_2","first-page":"17:1\u201317:17","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC\u201918)","author":"Daian E.","year":"2018","unstructured":"E. Daian, G. Losa, Y. Afek, and E. Gafni. 2018. A wealth of sub-consensus deterministic objects. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC\u201918). 17:1\u201317:17."},{"key":"e_1_3_2_26_2","series-title":"Proceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016)","first-page":"7:1\u20137:15","volume":"70","author":"Delporte-Gallet C.","year":"2017","unstructured":"C. Delporte-Gallet, H. Fauconnier, E. Gafni, and P. Kuznetsov. 2017. Set-consensus collections are decidable. In Proceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 70)). 7:1\u20137:15."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.013"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/365559.365617"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212749"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384008"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24922-9_17"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405727"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.027"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/645949.675309"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0042-0"},{"key":"e_1_3_2_37_2","first-page":"327","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures","author":"Herlihy M.","year":"1991","unstructured":"M. Herlihy. 1991. Impossibility results for asynchronous PRAM. In Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures. 327\u2013336."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.04.007"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892333"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/850929.851942"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09993-9_10"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/164051.164070"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263888"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786227"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798335766"},{"key":"e_1_3_2_49_2","first-page":"163","article-title":"Memory requirements for agreement among unreliable asynchronous processes","volume":"4","author":"Loui M. C.","year":"1987","unstructured":"M. C. Loui and H. Abu-Amara. 1987. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research 4 (1987), 163\u2013183.","journal-title":"Advances in Computing Research"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.11.007"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(95)00009-H"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90052-4"},{"issue":"7","key":"e_1_3_2_53_2","first-page":"1","article-title":"Algorithms in nature: The convergence of systems biology and computational thinking","volume":"546","author":"Navlakha S.","year":"2011","unstructured":"S. Navlakha and Z. Bar-Joseph. 2011. Algorithms in nature: The convergence of systems biology and computational thinking. Molecular Systems Biology 546, 7 (2011), 1\u201311.","journal-title":"Molecular Systems Biology"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2678280"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288965"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.5555\/645951.675479"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79527-6_9"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.5555\/6649"},{"key":"e_1_3_2_60_2","volume-title":"Proceedings of the 8th International Conference on Networked Systems (NETYS\u201920)","author":"Raynal M.","year":"2020","unstructured":"M. Raynal and G. Taubenfeld. 2020. Fully anonymous consensus and set agreement algorithms. In Proceedings of the 8th International Conference on Networked Systems (NETYS\u201920)."},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.105938"},{"key":"e_1_3_2_62_2","article-title":"Corrigendum: Mutual exclusion in fully anonymous shared memory systems","author":"Raynal M.","year":"2022","unstructured":"M. Raynal and G. Taubenfeld. 2022. Corrigendum: Mutual exclusion in fully anonymous shared memory systems. Inform. Process. Lett. (2022). Submitted to IPL for correction of [60].","journal-title":"Inform. Process. Lett."},{"key":"e_1_3_2_63_2","article-title":"Symmetry and anonymity in shared memory concurrent systems","volume":"136","author":"Raynal M.","year":"2022","unstructured":"M. Raynal and G. Taubenfeld. 2022. Symmetry and anonymity in shared memory concurrent systems. Bulletin of the European Association of Theoretical Computer Science (EATCS) 136 (2022). 17 pages.","journal-title":"Bulletin of the European Association of Theoretical Computer Science (EATCS)"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.03.030"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797329439"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307698"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259479"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0272-0"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/72981.72993"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90221-3"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.5555\/1211700"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35668-1_29"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087807"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24922-9_20"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050034"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.481599"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897565"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3529752","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3529752","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:24Z","timestamp":1750188684000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3529752"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,16]]},"references-count":76,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3529752"],"URL":"https:\/\/doi.org\/10.1145\/3529752","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,16]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}