{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:49:23Z","timestamp":1750308563359,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,1,20]],"date-time":"2016-01-20T00:00:00Z","timestamp":1453248000000},"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":["SIGOPS Oper. Syst. Rev."],"published-print":{"date-parts":[[2016,1,20]]},"abstract":"<jats:p>Among all classes of parallel programming abstractions, lock-free data structures are considered one of the most scalable and efficient thanks to their fine-grained style of synchronization. However, they are also challenging for developers and tools to verify because of the huge number of possible interleavings that result from finegrained synchronizations.<\/jats:p>\n          <jats:p>This paper addresses this fundamental problem between performance and verifiability of lock-free data structure implementations. We present TXIT, a system that greatly reduces the set of possible interleavings by inserting transactions into the implementation of a lock-free data structure. We leverage hardware transactional memory support from Intel Haswell processors to enforce these artificial transactions. Evaluation on six popular lock-free data structure libraries shows that TXIT makes it easy to verify lock-free data structures while incurring acceptable runtime overhead. Further analysis shows that two inefficiencies in Haswell are the largest contributors to this overhead.<\/jats:p>","DOI":"10.1145\/2883591.2883603","type":"journal-article","created":{"date-parts":[[2016,1,26]],"date-time":"2016-01-26T13:25:01Z","timestamp":1453814701000},"page":"57-63","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Making Lock-free Data Structures Verifiable with Artificial Transactions"],"prefix":"10.1145","volume":"49","author":[{"given":"Xinhao","family":"Yuan","sequence":"first","affiliation":[{"name":"Columbia University"}]},{"given":"David","family":"Williams-King","sequence":"additional","affiliation":[{"name":"Columbia University"}]},{"given":"Junfeng","family":"Yang","sequence":"additional","affiliation":[{"name":"Columbia University"}]},{"given":"Simha","family":"Sethumadhavan","sequence":"additional","affiliation":[{"name":"Columbia University"}]}],"member":"320","published-online":{"date-parts":[[2016,1,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Boost::Lockfree. http:\/\/www.boost.org\/doc\/libs\/1_55_0\/doc\/html\/lockfree.html.  Boost::Lockfree. http:\/\/www.boost.org\/doc\/libs\/1_55_0\/doc\/html\/lockfree.html."},{"key":"e_1_2_1_2_1","unstructured":"Folly C++ library. http:\/\/github.com\/facebook\/folly.  Folly C++ library. http:\/\/github.com\/facebook\/folly."},{"key":"e_1_2_1_3_1","unstructured":"Java's lock-free concurrency. http:\/\/www.pwendell.com\/2012\/08\/13\/java-lock-free deepdive.html.  Java's lock-free concurrency. http:\/\/www.pwendell.com\/2012\/08\/13\/java-lock-free deepdive.html."},{"key":"e_1_2_1_4_1","unstructured":"liblfds. http:\/\/liblfds.org.  liblfds. http:\/\/liblfds.org."},{"key":"e_1_2_1_5_1","unstructured":"Lock-free code: A false sense of security. http:\/\/www.drdobbs.com\/cpp\/lock-free-code-a-false-sense-ofsecurity\/210600279.  Lock-free code: A false sense of security. http:\/\/www.drdobbs.com\/cpp\/lock-free-code-a-false-sense-ofsecurity\/210600279."},{"key":"e_1_2_1_6_1","unstructured":"Are all of the new concurrent collections lock-free? http:\/\/blogs.msdn.com\/b\/pfxteam\/archive\/2010\/01\/26\/9953725.aspx.  Are all of the new concurrent collections lock-free? http:\/\/blogs.msdn.com\/b\/pfxteam\/archive\/2010\/01\/26\/9953725.aspx."},{"key":"e_1_2_1_7_1","unstructured":"nbds. http:\/\/nbds.googlecode.com.  nbds. http:\/\/nbds.googlecode.com."},{"key":"e_1_2_1_8_1","unstructured":"Pyevolve. http:\/\/pyevolve.sourceforge.net\/.  Pyevolve. http:\/\/pyevolve.sourceforge.net\/."},{"key":"e_1_2_1_9_1","unstructured":"Aba problem on wikipedia. http:\/\/en.wikipedia.org\/wiki\/ABA_problem.  Aba problem on wikipedia. http:\/\/en.wikipedia.org\/wiki\/ABA_problem."},{"key":"e_1_2_1_10_1","volume-title":"https:\/\/software.intel.com\/en-us\/blogs\/2012\/02\/07\/transactional-synchronization-in-haswell","author":"Transactional","year":"2012","unstructured":"Transactional synchronization in haswell. https:\/\/software.intel.com\/en-us\/blogs\/2012\/02\/07\/transactional-synchronization-in-haswell , 2012 . Transactional synchronization in haswell. https:\/\/software.intel.com\/en-us\/blogs\/2012\/02\/07\/transactional-synchronization-in-haswell, 2012."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/L-CA.2006.18"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273442.1250737"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1809028.1806634"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250662.1250697"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040315"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-60761-7","volume-title":"Partial-Order Methods for the Verification of Concurrent Systems: An Approach to the State-Explosion Problem","author":"Godefroid P.","year":"1996","unstructured":"P. Godefroid . Partial-Order Methods for the Verification of Concurrent Systems: An Approach to the State-Explosion Problem . Springer-Verlag New York, Inc. , Secaucus, NJ, USA , 1996 . ISBN 3540607617. P. Godefroid. Partial-Order Methods for the Verification of Concurrent Systems: An Approach to the State-Explosion Problem. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1996. ISBN 3540607617."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263717"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043582"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007944"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/173682.165164"},{"volume-title":"June","year":"2014","key":"e_1_2_1_21_1","unstructured":"Intel. Intel 64 and IA-32 Architectures Software Developer's Manual Volume 1: Basic Architecture , June 2014 . Intel. Intel 64 and IA-32 Architectures Software Developer's Manual Volume 1: Basic Architecture, June 2014."},{"volume-title":"March","year":"2014","key":"e_1_2_1_22_1","unstructured":"Intel. Intel 64 and IA-32 Architectures Optimization Reference Manual , March 2014 . Intel. Intel 64 and IA-32 Architectures Optimization Reference Manual, March 2014."},{"key":"e_1_2_1_23_1","first-page":"18","volume-title":"Proceedings of the 4th USENIX Conference on Networked Systems Design & Implementation, NSDI'07","author":"Killian C.","year":"2007","unstructured":"C. Killian , J. W. Anderson , R. Jhala , and A. Vahdat . Life, death, and the critical transition: Finding liveness bugs in systems code . In Proceedings of the 4th USENIX Conference on Networked Systems Design & Implementation, NSDI'07 , pages 18 -- 18 , Berkeley, CA, USA , 2007 . USENIX Association. URL http:\/\/dl.acm.org\/citation.cfm?id=1973430.1973448. C. Killian, J. W. Anderson, R. Jhala, and A. Vahdat. Life, death, and the critical transition: Finding liveness bugs in systems code. In Proceedings of the 4th USENIX Conference on Networked Systems Design & Implementation, NSDI'07, pages 18--18, Berkeley, CA, USA, 2007. USENIX Association. URL http:\/\/dl.acm.org\/citation.cfm?id=1973430.1973448."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2008.4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/996893.996848"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250785"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844136"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00625968"},{"key":"e_1_2_1_31_1","first-page":"3","volume-title":"Proceedings of the 5th International Conference on Systems Software Verification, SSV'10","author":"Simsa J.","year":"2010","unstructured":"J. Simsa , R. Bryant , and G. Gibson . dbug: Systematic evaluation of distributed systems . In Proceedings of the 5th International Conference on Systems Software Verification, SSV'10 , pages 3 -- 3 , Berkeley, CA, USA , 2010 . USENIX Association. URL http:\/\/dl.acm.org\/citation.cfm?id=1929004.1929007. J. Simsa, R. Bryant, and G. Gibson. dbug: Systematic evaluation of distributed systems. In Proceedings of the 5th International Conference on Systems Software Verification, SSV'10, pages 3--3, Berkeley, CA, USA, 2010. USENIX Association. URL http:\/\/dl.acm.org\/citation.cfm?id=1929004.1929007."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882291.1882301"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022920129859"},{"key":"e_1_2_1_34_1","first-page":"229","volume-title":"NSDI","volume":"9","author":"Yabandeh M.","year":"2009","unstructured":"M. Yabandeh , N. Knezevic , D. Kostic , and V. Kuncak . Crystalball: Predicting and preventing inconsistencies in deployed distributed systems . In NSDI , volume 9 , pages 229 -- 244 , 2009 . M. Yabandeh, N. Knezevic, D. Kostic, and V. Kuncak. Crystalball: Predicting and preventing inconsistencies in deployed distributed systems. In NSDI, volume 9, pages 229--244, 2009."},{"key":"e_1_2_1_35_1","first-page":"10","volume-title":"Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation --","volume":"7","author":"Yang J.","year":"2006","unstructured":"J. Yang , C. Sar , and D. Engler . Explode: A lightweight, general system for finding serious storage system errors . In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation -- Volume 7 , OSDI '06, pages 10 -- 10 , Berkeley, CA, USA , 2006 . USENIX Association. URL http:\/\/dl.acm.org\/citation.cfm?id=1267308.1267318. J. Yang, C. Sar, and D. Engler. Explode: A lightweight, general system for finding serious storage system errors. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation -- Volume 7, OSDI '06, pages 10--10, Berkeley, CA, USA, 2006. USENIX Association. URL http:\/\/dl.acm.org\/citation.cfm?id=1267308.1267318."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189256.1189259"},{"key":"e_1_2_1_37_1","first-page":"213","volume-title":"Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI'09","author":"Yang J.","year":"2009","unstructured":"J. Yang , T. Chen , M. Wu , Z. Xu , X. Liu , H. Lin , M. Yang , F. Long , L. Zhang , and L. Zhou . Modist: Transparent model checking of unmodified distributed systems . In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI'09 , pages 213 -- 228 , Berkeley, CA, USA , 2009 . USENIX Association. URL http:\/\/dl.acm.org\/citation.cfm?id=1558977.1558992. J. Yang, T. Chen, M. Wu, Z. Xu, X. Liu, H. Lin, M. Yang, F. Long, L. Zhang, and L. Zhou. Modist: Transparent model checking of unmodified distributed systems. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI'09, pages 213--228, Berkeley, CA, USA, 2009. USENIX Association. URL http:\/\/dl.acm.org\/citation.cfm?id=1558977.1558992."}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2883591.2883603","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2883591.2883603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:12Z","timestamp":1750273452000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2883591.2883603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,20]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,1,20]]}},"alternative-id":["10.1145\/2883591.2883603"],"URL":"https:\/\/doi.org\/10.1145\/2883591.2883603","relation":{},"ISSN":["0163-5980"],"issn-type":[{"type":"print","value":"0163-5980"}],"subject":[],"published":{"date-parts":[[2016,1,20]]},"assertion":[{"value":"2016-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}