{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:24Z","timestamp":1750307784951,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T00:00:00Z","timestamp":1196467200000},"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":[[2007,12]]},"abstract":"<jats:p>\n            A snapshot object is an abstraction of the problem of obtaining a consistent view of the contents of shared memory in a distributed system, despite concurrent changes to the memory. There are implementations of\n            <jats:italic>m<\/jats:italic>\n            -component snapshot objects shared by\n            <jats:italic>n<\/jats:italic>\n            \u2265\n            <jats:italic>m<\/jats:italic>\n            processes using\n            <jats:italic>m<\/jats:italic>\n            registers. This is the minimum number of registers possible. We prove a time lower bound for implementations that use this minimum number of registers. It matches the time taken by the fastest such implementation. Our proof yields insight into the structure of any such implementation, showing that processes must access the registers in a very constrained way. We also prove a time lower bound for snapshot implementations using single-writer registers in addition to\n            <jats:italic>m<\/jats:italic>\n            historyless objects (such as registers and swap objects).\n          <\/jats:p>","DOI":"10.1145\/1314690.1314694","type":"journal-article","created":{"date-parts":[[2007,12,7]],"date-time":"2007-12-07T19:19:01Z","timestamp":1197055141000},"page":"30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Time lower bounds for implementations of multi-writer snapshots"],"prefix":"10.1145","volume":"54","author":[{"given":"Faith","family":"Ellen","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiota","family":"Fatourou","sequence":"additional","affiliation":[{"name":"University of Ioannina, Ioannina, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Ruppert","sequence":"additional","affiliation":[{"name":"York University, Toronto, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,12]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/153724.153741"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/343477.343523"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1007\/BF02242703"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/BF02280833"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1006\/inco.1996.0006"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1006\/jagm.1993.1022"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1016\/0196-6774(90)90021-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/97444.97701"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1007\/11947950_35"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1011767.1011777"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1137\/S0097539700366000"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1007\/BF02242714"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/179812.179902"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1137\/S0097539795279463"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.5555\/983102"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1006\/inco.1993.1065"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1132516.1132542"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/290179.290183"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1007\/s00446-003-0091-y"},{"volume":"601","volume-title":"Proceedings of the Israel Symposium on the Theory of Computing and Systems. Lecture Notes in Computer Science","author":"Gawlick R.","key":"e_1_2_1_20_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/112600.112602"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/114005.102808"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/78969.78972"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1137\/S0097539701397412"},{"volume":"857","volume-title":"Proceedings of the 8th International Workshop on Distributed Algorithms. Lecture Notes in Computer Science","author":"Inoue M.","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/BF01185868"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1016\/S0020-0190(97)00189-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1060590.1060697"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1137\/S0097539797317299"},{"volume-title":"Distributed Algorithms. Morgan Kaufmann","author":"Lynch N. A.","key":"e_1_2_1_30_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1016\/S0304-3975(00)00412-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1137\/S0097539797329439"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1314690.1314694","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1314690.1314694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:11Z","timestamp":1750254971000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1314690.1314694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["10.1145\/1314690.1314694"],"URL":"https:\/\/doi.org\/10.1145\/1314690.1314694","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2007,12]]},"assertion":[{"value":"2007-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}