{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T19:18:32Z","timestamp":1770578312129,"version":"3.49.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,1,9]],"date-time":"2015-01-09T00:00:00Z","timestamp":1420761600000},"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. Archit. Code Optim."],"published-print":{"date-parts":[[2015,1,9]]},"abstract":"<jats:p>Transactional memory systems providing snapshot isolation enable concurrent access to shared data without incurring aborts on read-write conflicts. Reducing aborts is extremely relevant as it leads to higher concurrency, greater performance, and better predictability. Unfortunately, snapshot isolation does not provide serializability as it allows certain anomalies that can lead to subtle consistency violations. While some mechanisms have been proposed to verify the correctness of a program utilizing snapshot isolation transactions, it remains difficult to repair incorrect applications. To reduce the programmer\u2019s burden in this case, we present a technique based on dynamic code and graph dependency analysis that automatically corrects existing snapshot isolation anomalies in transactional memory programs. Our evaluation shows that corrected applications retain the performance benefits characteristic of snapshot isolation over conventional transactional memory systems.<\/jats:p>","DOI":"10.1145\/2693260","type":"journal-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T20:02:10Z","timestamp":1421092930000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Efficient Correction of Anomalies in Snapshot Isolation Transactions"],"prefix":"10.1145","volume":"11","author":[{"given":"Heiner","family":"Litz","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Ricardo J.","family":"Dias","sequence":"additional","affiliation":[{"name":"NOVA-LINCS, NOVA University of Lisbon, Caparica, Portugal"}]},{"given":"David R.","family":"Cheriton","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]}],"member":"320","published-online":{"date-parts":[[2015,1,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497466"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2005.41"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69501-1_21"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 2nd ACM SIGPLAN Workshop on Transactional Computing.","author":"Aydonat Utku","year":"2008","unstructured":"Utku Aydonat and Tarek Abdelrahman . 2008 . Serializability of transactions in software transactional memory . In Proceedings of the 2nd ACM SIGPLAN Workshop on Transactional Computing. Utku Aydonat and Tarek Abdelrahman. 2008. Serializability of transactions in software transactional memory. In Proceedings of the 2nd ACM SIGPLAN Workshop on Transactional Computing."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2010.25"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223785"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454128"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2008.24"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376690"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201908)","author":"Minh Chi Cao","year":"2008","unstructured":"Chi Cao Minh , JaeWoong Chung , Christos Kozyrakis , and Kunle Olukotun . 2008 . STAMP: Stanford transactional applications for multi-processing . In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201908) . Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. 2008. STAMP: Stanford transactional applications for multi-processing. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201908)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150019.1136506"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168903"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90007-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_28"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 3rd USENIX Conference on Hot Topics in Parallelism (HotPar\u201911)","author":"Dias Ricardo J.","unstructured":"Ricardo J. Dias , Jo\u00e3o M. Louren &cogon;o, and Nuno M . Pregui&cogon;a. 2011. Efficient and correct transactional memory programs combining snapshot isolation and static analysis . In Proceedings of the 3rd USENIX Conference on Hot Topics in Parallelism (HotPar\u201911) . Usenix Association. Ricardo J. Dias, Jo\u00e3o M. Louren&cogon;o, and Nuno M. Pregui&cogon;a. 2011. Efficient and correct transactional memory programs combining snapshot isolation and static analysis. In Proceedings of the 3rd USENIX Conference on Hot Topics in Parallelism (HotPar\u201911). Usenix Association."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_14"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071615"},{"key":"e_1_2_1_19_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and intractability. Vol. 174 . Freeman , New York, NY. Michael R. Garey and David S. Johnson. 1979. Computers and intractability. Vol. 174. Freeman, New York, NY."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273029"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/998680.1006711"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165164"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2490301.2451173"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB\u201907)","author":"Jorwekar Sudhir","unstructured":"Sudhir Jorwekar , Alan Fekete , Krithi Ramamritham , and S. Sudarshan . 2007. Automating the detection of snapshot isolation anomalies . In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB\u201907) . VLDB Endowment, Vienna, Austria, 1263--1274. Sudhir Jorwekar, Alan Fekete, Krithi Ramamritham, and S. Sudarshan. 2007. Automating the detection of snapshot isolation anomalies. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB\u201907). VLDB Endowment, Vienna, Austria, 1263--1274."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402718"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 9th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT\u201914)","author":"Kuru Ismail","year":"2014","unstructured":"Ismail Kuru , Burcu Kulahcioglu Ozkan , Suha Orhun Mutluergil , Serdar Tasiran , Tayfun Elmas , and Ernie Cohen . 2014 . Verifying programs under snapshot isolation and similar relaxed consistency models . In Proceedings of the 9th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT\u201914) . Ismail Kuru, Burcu Kulahcioglu Ozkan, Suha Orhun Mutluergil, Serdar Tasiran, Tayfun Elmas, and Ernie Cohen. 2014. Verifying programs under snapshot isolation and similar relaxed consistency models. In Proceedings of the 9th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT\u201914)."},{"key":"e_1_2_1_27_1","volume-title":"Cormen","author":"Leiserson Charles E.","year":"2001","unstructured":"Charles E. Leiserson , Ronald L. Rivest , Clifford Stein , and Thomas H . Cormen . 2001 . Introduction to Algorithms. MIT Press , Cambridge, MA. Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, and Thomas H. Cormen. 2001. Introduction to Algorithms. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541952"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064978.1065034"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT\u201906)","author":"Marathe Virendra J.","unstructured":"Virendra J. Marathe , Michael F. Spear , Christopher Heriot , Athul Acharya , David Eisenstat , William N. Scherer III, and Michael L. Scott . 2006. Lowering the overhead of nonblocking software transactional memory . In Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT\u201906) . Virendra J. Marathe, Michael F. Spear, Christopher Heriot, Athul Acharya, David Eisenstat, William N. Scherer III, and Michael L. Scott. 2006. Lowering the overhead of nonblocking software transactional memory. In Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT\u201906)."},{"key":"e_1_2_1_31_1","unstructured":"Intel Corporation. 2012. Chapter 8: Intel transactional synchronization extensions. In Intel Architecture Instruction Set Extensions Programming Reference.  Intel Corporation. 2012. Chapter 8: Intel transactional synchronization extensions. In Intel Architecture Instruction Set Extensions Programming Reference."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 12th International Symposium on High-Performance Computer Architecture (HPCA-12)","author":"Moore Kevin E.","unstructured":"Kevin E. Moore , Jayaram Bobba , Michelle J. Moravan , Mark D. Hill , and David A. Wood . 2006. LogTM: Log-based transactional memory . In Proceedings of the 12th International Symposium on High-Performance Computer Architecture (HPCA-12) . IEEE Computer Society, Austin, TX. Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill, and David A. Wood. 2006. LogTM: Log-based transactional memory. In Proceedings of the 12th International Symposium on High-Performance Computer Architecture (HPCA-12). IEEE Computer Society, Austin, TX."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804677"},{"key":"e_1_2_1_35_1","volume-title":"Papadimitriou and Kenneth Steiglitz","author":"Christos","year":"1998","unstructured":"Christos H. Papadimitriou and Kenneth Steiglitz . 1998 . Combinatorial optimization: algorithms and complexity. Courier Dover Publications , North Chelmsford, MA. Christos H. Papadimitriou and Kenneth Steiglitz. 1998. Combinatorial optimization: algorithms and complexity. Courier Dover Publications, North Chelmsford, MA."},{"key":"e_1_2_1_36_1","volume-title":"A simple probabilistic approximation algorithm for vertex cover","author":"Pitt Leonard Brian","unstructured":"Leonard Brian Pitt . 1985. A simple probabilistic approximation algorithm for vertex cover . Yale University , Department of Computer Science, New Haven, CT. Leonard Brian Pitt. 1985. A simple probabilistic approximation algorithm for vertex cover. Yale University, Department of Computer Science, New Haven, CT."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367523"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2665671.2665734"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/605397.605399"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2005.54"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1521747.1521799"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1504176.1504201"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767853"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT\u201906)","author":"Riegel Torvald","year":"2006","unstructured":"Torvald Riegel , Christof Fetzer , and Pascal Felber . 2006 . Snapshot isolation for software transactional memory . In Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT\u201906) . Torvald Riegel, Christof Fetzer, and Pascal Felber. 2006. Snapshot isolation for software transactional memory. In Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT\u201906)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485922.2485963"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.2012.6272111"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1669112.1669132"},{"key":"e_1_2_1_48_1","first-page":"11","article-title":"TPC-C Benchmark","volume":"5","author":"Transaction Processing Performance Council","year":"2010","unstructured":"Transaction Processing Performance Council . 2010 . TPC-C Benchmark , Revision 5 . 11 . Transaction Processing Performance Council. 2010. TPC-C Benchmark, Revision 5.11.","journal-title":"Revision"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503232"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2693260","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2693260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:31Z","timestamp":1750227211000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2693260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,9]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1,9]]}},"alternative-id":["10.1145\/2693260"],"URL":"https:\/\/doi.org\/10.1145\/2693260","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,9]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}