{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:10:05Z","timestamp":1787389805920,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>The atomic snapshot object is an important primitive used for the design and verification of wait-free algorithms in shared-memory distributed systems. A snapshot object is a shared data structure partitioned into segments. Processors can either update an individual segment or instantaneously scan all segments of the object. This paper presents an implementation of an atomic snapshot object in which each high-level operation (scan or update) requires O(n log n) low-level operations on atomic read\/write registers.<\/jats:p>","DOI":"10.1137\/s0097539795279463","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"319-340","source":"Crossref","is-referenced-by-count":66,"title":["Atomic Snapshots in\n                    <i>O<\/i>\n                    (\n                    <i>n<\/i>\n                    log\n                    <i>n<\/i>\n                    ) Operations"],"prefix":"10.1137","volume":"27","author":[{"given":"Hagit","family":"Attiya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ophir","family":"Rachman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153741"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242703"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"J. Aspnes,\n                      Time\u2010 and Space\u2010Efficient Randomized Consensus\n                      , Proc. of the 9th Annual ACM Symposium on Principles of Distributed Computing, 1990, pp. 325\u2013331.","DOI":"10.1145\/93385.93433"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"J. Aspnes and M. P. Herlihy,\n                      Wait\u2010Free Data Structures in the Asynchronous PRAM Model\n                      , Proceedings of the 2nd Annual Symposium on Parallel Algorithms and Architectures, 1990, pp. 340\u2013349.","DOI":"10.1145\/97444.97701"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"H. Attiya, A. Bar\u2010Noy and D. Dolev,\n                      Sharing Memory Robustly in Message\u2010Passing Systems\n                      , Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, 1990, pp. 363\u2013376.","DOI":"10.1145\/93385.93441"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"H. Attiya, D. Dolev and N. Shavit,\n                      Bounded Polynomial Randomized Consensus\n                      , Proceedings ofthe 8th Annual ACM Symposium on Principles of Distributed Computing, 1989, pp. 281\u2013293.","DOI":"10.1145\/72981.73001"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"H. Attiya, M. Herlihy and O. Rachman,\n                      Atomic Snapshots Using Lattice Agreement\n                      , Distributed Computing, Vol. 8, in press. Also: Proceedings of the 6th International Workshop on Distributed Algorithms, Haifa, Israel, November 1992, A. Segall and S. Zaks, eds., pp. 35\u201353.","DOI":"10.1007\/3-540-56188-9_3"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/179812.179902"},{"key":"R9","unstructured":"T. Chandra and C. Dwork,\n                      Using Consensus to Solve Atomic Snapshots\n                      , unpublished manuscript."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"D. Dolev and N. Shavit,\n                      Bounded Concurrent Time\u2010Stamp Systems Are Constructible!\n                      , SIAM J. Comput., to appear. Also: Proceedings of the 21st ACM Symposium on Theory of Computing, 1989, pp. 454\u2013465.","DOI":"10.21236\/ADA213853"},{"key":"R11","unstructured":"C. Dwork, private communication."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. P. Herlihy, S. A. Plotkin, and O. Waarts,\n                      Time\u2010Lapse Snapshots\n                      , Proceedings of the Israel Symposium on the Theory of Computing and Systems, Haifa, Israel, May 1992, D. Dolev, Z. Galil, and M. Rodeh, eds., Lecture Notes in Computer Science #601, Springer\u2010Verlag, pp. 154\u2013170.","DOI":"10.1007\/BFb0035175"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. M. Herlihy and O. Waarts,\n                      Bounded Round Numbers\n                      , Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing, New York, 1993, pp. 53\u201364.","DOI":"10.1145\/164051.164058"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"C. Dwork and O. Waarts,\n                      Simple and Efficient Concurrent Timestamping or Bounded Concurrent Timestamping are Comprehensible\n                      , Proceedings of the 24th ACM Symposium on Theory of Computing, 1992, pp. 655\u2013666. Also: IBM Research Report RJ 8425, October 1991.","DOI":"10.1145\/129712.129776"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Rainer Gawlick, Nancy Lynch, Nir Shavit, Concurrent timestamping made simple, Lecture Notes in Comput. Sci., Vol. 601, Springer, Berlin, 1992, 171\u20131831233836","DOI":"10.1007\/BFb0035176"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. P. Herlihy,\n                      Randomized Wait\u2010Free Objects\n                      , Proceedings of the 10th ACM Symp. on Principles of Distributed Computing, 1991, pp. 11\u201321.","DOI":"10.1145\/112600.112602"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Michiko Inoue, Wei Chen, Toshimitsu Masuzawa, Nobuki Tokura, Linear\u2010time snapshot using multi\u2010writer multi\u2010reader registers, Lecture Notes in Comput. Sci., Vol. 857, Springer, Berlin, 1994, 130\u20131401325247","DOI":"10.1007\/BFb0020429"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242708"},{"key":"R21","unstructured":"A. Israeli and A. Shirazi,\n                      Efficient Snapshot Protocol Using 2\u2010Lattice Agreement\n                      , unpublished manuscript."},{"key":"R22","unstructured":"A. Israeli and A. Shirazi,\n                      The Complexity of Updating Snapshot Objects\n                      , unpublished manuscript."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Amos Israeli, Amnon Shaham, Asaf Shirazi, Linear\u2010time snapshot protocols for unbalanced systems, Lecture Notes in Comput. Sci., Vol. 725, Springer, Berlin, 1993, 26\u20133895d:68040","DOI":"10.1007\/3-540-57271-6_25"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"L. M. Kirousis, P. Spirakis, and Ph. Tsigas,\n                      Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity\n                      , Proceedings of the 5th International Workshop on Distributed Algorithms, S. Toueg, P. Spirakis, and L. Kirousis, eds., Delphi, Greece, October 1991, Lecture Notes in Computer Science #579, Springer\u2010Verlag, pp. 229\u2013241.","DOI":"10.1007\/BFb0022450"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795279463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:04Z","timestamp":1787335924000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795279463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795279463"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795279463","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}