{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:18Z","timestamp":1750307778137,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"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":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            This article considers the problem of robustly emulating a shared atomic memory over a distributed message-passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context and introduce a generic algorithm that emulates an atomic memory. The algorithm is instantiated for various settings according to whether processes have access to local stable storage, and whether, in every execution of the algorithm, a sufficient number of processes are assumed not to crash. We establish the optimality of specific instances of our algorithm in terms of\n            <jats:italic>resilience<\/jats:italic>\n            ,\n            <jats:italic>log complexity<\/jats:italic>\n            (number of stable storage accesses needed in every read or write operation), as well as\n            <jats:italic>time complexity<\/jats:italic>\n            (number of communication steps needed in every read or write operation). The article also discusses the impact of considering a multiwriter versus a single-writer memory, as well as the impact of weakening the consistency of the memory by providing safe or regular semantics instead of atomicity.\n          <\/jats:p>","DOI":"10.1145\/1328911.1328923","type":"journal-article","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T16:08:32Z","timestamp":1207066112000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["The collective memory of amnesic processes"],"prefix":"10.1145","volume":"4","author":[{"given":"Rachid","family":"Guerraoui","sequence":"first","affiliation":[{"name":"School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ron R.","family":"Levy","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bastian","family":"Pochon","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jim","family":"Pugh","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"e_1_2_1_1_1","article-title":"Failure detection and consensus in the crash-recovery model. In Proceedings of the 12th International Symposium on Distributed Computing (DISC). Also ACM","author":"Aguilera M.","year":"1998","unstructured":"Aguilera , M. , Chen , W. , and Toueg , S. 1998 . Failure detection and consensus in the crash-recovery model. In Proceedings of the 12th International Symposium on Distributed Computing (DISC). Also ACM Trans. Program. Lang. Syst. 231--245. Aguilera, M., Chen, W., and Toueg, S. 1998. Failure detection and consensus in the crash-recovery model. In Proceedings of the 12th International Symposium on Distributed Computing (DISC). Also ACM Trans. Program. Lang. Syst. 231--245.","journal-title":"Trans. Program. Lang. Syst. 231--245."},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1006\/jagm.1999.1025"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/200836.200869"},{"unstructured":"Attiya H. and Welch J. 1998. Distributed Computing Fundamentals Simulations and Advanced Topics. McGraw-Hill International UK.   Attiya H. and Welch J. 1998. Distributed Computing Fundamentals Simulations and Advanced Topics. McGraw-Hill International UK.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1016\/j.jpdc.2004.10.008"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/1011767.1011802"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/114005.102808"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/78969.78972"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1080\/00029890.1995.12004627"},{"issue":"1986","key":"e_1_2_1_10_1","first-page":"77","article-title":"On interprocess communication - Part i: Basic formalism, Part ii: Algorithms. DEC SRC Rep. 8","volume":"1","author":"Lamport L.","year":"1985","unstructured":"Lamport , L. 1985 . On interprocess communication - Part i: Basic formalism, Part ii: Algorithms. DEC SRC Rep. 8 . Also in Distrib. Comput. 1 ( 1986 ), 77 -- 101 . Lamport, L. 1985. On interprocess communication - Part i: Basic formalism, Part ii: Algorithms. DEC SRC Rep. 8. Also in Distrib. Comput. 1 (1986), 77--101.","journal-title":"Also in Distrib. Comput."},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/359545.359563"},{"volume-title":"Distributed Algorithms. Morgan Kaufmann","author":"Lynch N.","unstructured":"Lynch , N. 1996. Distributed Algorithms. Morgan Kaufmann , San Mateo, CA . Lynch, N. 1996. Distributed Algorithms. Morgan Kaufmann, San Mateo, CA.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 16th International Symposium on Distributed Computing (DISC).","author":"Lynch N.","unstructured":"Lynch , N. , and Shvartsman , A . 2002. Rambo: A reconfigurable atomic memory service for dynamic networks . In Proceedings of the 16th International Symposium on Distributed Computing (DISC). Lynch, N., and Shvartsman, A. 2002. Rambo: A reconfigurable atomic memory service for dynamic networks. In Proceedings of the 16th International Symposium on Distributed Computing (DISC).","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the 27th International Symposium on Fault-Tolerant Computing Systems (FTCS).","author":"Lynch N.","unstructured":"Lynch , N. , and Shvartsman , A . 1997. Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts . In Proceedings of the 27th International Symposium on Fault-Tolerant Computing Systems (FTCS). Lynch, N., and Shvartsman, A. 1997. Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts. In Proceedings of the 27th International Symposium on Fault-Tolerant Computing Systems (FTCS).","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the 17th International Symposium on Distributed Computing (DISC).","author":"Shao C.","unstructured":"Shao , C. , Pierce , E. , and Welch , J . 2003. Multi-Writer consistency conditions for shared memory objects . In Proceedings of the 17th International Symposium on Distributed Computing (DISC). Shao, C., Pierce, E., and Welch, J. 2003. Multi-Writer consistency conditions for shared memory objects. In Proceedings of the 17th International Symposium on Distributed Computing (DISC).","key":"e_1_2_1_15_1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328923","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328911.1328923","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:03Z","timestamp":1750254963000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328923"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1328911.1328923"],"URL":"https:\/\/doi.org\/10.1145\/1328911.1328923","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}