{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,24]],"date-time":"2025-12-24T12:35:59Z","timestamp":1766579759571,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,4,1]],"date-time":"2011-04-01T00:00:00Z","timestamp":1301616000000},"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":[[2011,4]]},"abstract":"<jats:p>\n            This article deals with the emulation of atomic read\/write (R\/W) storage in\n            <jats:italic>dynamic<\/jats:italic>\n            asynchronous message passing systems. In static settings, it is well known that atomic R\/W storage can be implemented in a fault-tolerant manner even if the system is completely asynchronous, whereas consensus is not solvable. In contrast, all existing emulations of atomic storage in dynamic systems rely on consensus or stronger primitives, leading to a popular belief that dynamic R\/W storage is unattainable without consensus.\n          <\/jats:p>\n          <jats:p>In this article, we specify the problem of dynamic atomic read\/write storage in terms of the interface available to the users of such storage. We discover that, perhaps surprisingly, dynamic R\/W storage is solvable in a completely asynchronous system: we present DynaStore, an algorithm that solves this problem. Our result implies that atomic R\/W storage is in fact easier than consensus, even in dynamic systems.<\/jats:p>","DOI":"10.1145\/1944345.1944348","type":"journal-article","created":{"date-parts":[[2011,4,12]],"date-time":"2011-04-12T12:03:38Z","timestamp":1302609818000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":44,"title":["Dynamic atomic storage without consensus"],"prefix":"10.1145","volume":"58","author":[{"given":"Marcos K.","family":"Aguilera","sequence":"first","affiliation":[{"name":"Microsoft Research, Mountain View, CA"}]},{"given":"Idit","family":"Keidar","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Dahlia","family":"Malkhi","sequence":"additional","affiliation":[{"name":"Microsoft Research, Mountain View, CA"}]},{"given":"Alexander","family":"Shraer","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Santa Clara, CA"}]}],"member":"320","published-online":{"date-parts":[[2011,4,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153741"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200869"},{"key":"e_1_2_2_3_1","unstructured":"Birman K. Malkhi D. and van Renesse R. 2010. Virtually synchronous methodology for dynamic service replication. Tech. rep. MSR-TR-2010-151.  Birman K. Malkhi D. and van Renesse R. 2010. Virtually synchronous methodology for dynamic service replication. Tech. rep. MSR-TR-2010-151."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/248052.248120"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11795490_27"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/503112.503113"},{"key":"e_1_2_2_7_1","unstructured":"Cormen T. T. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. T. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/323647.323637"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734213.1734216"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(91)90037-X"},{"volume-title":"Proceedings of the the 20th International Conference on Distributed Computing Systems (ICDCS'00)","author":"Englert B.","key":"e_1_2_2_11_1"},{"volume-title":"Proceedings of the 17th International Symposium on Distributed Computing (DISC). 259--268","author":"Gilbert S.","key":"e_1_2_2_12_1"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786228"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582783"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237157"},{"volume-title":"Proceedings of the Symposium on Fault-Tolerant Computing. IEEE, 272--281","author":"Lynch N.","key":"e_1_2_2_18_1"},{"key":"e_1_2_2_19_1","unstructured":"Lynch N. A. 1996. Distributed Algorithms. Morgan Kaufmann San Francisco.   Lynch N. A. 1996. Distributed Algorithms. Morgan Kaufmann San Francisco."},{"volume-title":"Proceedings of the 5th International Symposium on Distributed Computing (DISC).","author":"Lynch N. A.","key":"e_1_2_2_20_1"},{"volume-title":"Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI 04)","author":"MacCormick J.","key":"e_1_2_2_21_1"},{"volume-title":"Proceedings of the International Conference on Dependable Systems and Networks.","author":"Martin J.-P.","key":"e_1_2_2_22_1"},{"volume-title":"Proceedings of the 13th International Conference on Very Large Data Bases (VLDB). 268--275","author":"Paris J.","key":"e_1_2_2_23_1"},{"volume-title":"Rosebud: A scalable byzantine-fault-tolerant storage architecture. Tech. rep. TR\/932, MIT LCS.","year":"2003","author":"Rodrigues R.","key":"e_1_2_2_24_1"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011847"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/98163.98167"},{"volume-title":"Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI 04)","author":"van Renesse R.","key":"e_1_2_2_27_1"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259424"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944345.1944348","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1944345.1944348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:30Z","timestamp":1750244370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944345.1944348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1145\/1944345.1944348"],"URL":"https:\/\/doi.org\/10.1145\/1944345.1944348","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2011,4]]},"assertion":[{"value":"2009-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}