{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:24:50Z","timestamp":1777965890816,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,31]],"date-time":"2018-03-31T00:00:00Z","timestamp":1522454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF OAC 1440530 and NSF OAC 1740095"],"award-info":[{"award-number":["NSF OAC 1440530 and NSF OAC 1740095"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>Nonblocking data structures allow scalable and thread-safe access to shared data. They provide individual operations that appear to execute atomically. However, it is often desirable to execute multiple operations atomically in a transactional manner. Previous solutions, such as Software Transactional Memory (STM) and transactional boosting, manage transaction synchronization separately from the underlying data structure\u2019s thread synchronization. Although this reduces programming effort, it leads to overhead associated with additional synchronization and the need to rollback aborted transactions. In this work, we present a new methodology for transforming high-performance lock-free linked data structures into high-performance lock-free transactional linked data structures without revamping the data structures\u2019 original synchronization design. Our approach leverages the semantic knowledge of the data structure to eliminate the overhead of false conflicts and rollbacks. We encapsulate all operations, operands, and transaction status in a transaction descriptor, which is shared among the nodes accessed by the same transaction. We coordinate threads to help finish the remaining operations of delayed transactions based on their transaction descriptors. When a transaction fails, we recover the correct abstract state by reversely interpreting the logical status of a node. We also present an obstruction-free version of our algorithm that can be applied to dynamic execution scenarios and an example of our approach applied to a hash map. In our experimental evaluation using transactions with randomly generated operations, our lock-free transactional data structures outperform the transactional boosted ones by 70% on average. They also outperform the alternative STM-based approaches by a factor of 2 to 13 across all scenarios. More importantly, we achieve 4,700 to 915,000 times fewer spurious aborts than the alternatives.<\/jats:p>","DOI":"10.1145\/3209690","type":"journal-article","created":{"date-parts":[[2018,6,15]],"date-time":"2018-06-15T14:14:38Z","timestamp":1529072078000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Lock-Free Transactional Transformation for Linked Data Structures"],"prefix":"10.1145","volume":"5","author":[{"given":"Deli","family":"Zhang","sequence":"first","affiliation":[{"name":"Microsoft, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Laborde","sequence":"additional","affiliation":[{"name":"University of Central Florida, Orlando, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lance","family":"Lebanoff","sequence":"additional","affiliation":[{"name":"University of Central Florida, Orlando, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damian","family":"Dechev","sequence":"additional","affiliation":[{"name":"University of Central Florida, Orlando, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835699"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835703"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454456.1454466"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375619"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837853.1693464"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508263"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_14"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835736"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190215.1190260"},{"key":"e_1_2_1_10_1","volume-title":"Cambridge University Computer Laboratory","author":"Fraser Keir","year":"2004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462172"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688511"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.42"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_15"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378587"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345233"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855056"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645958.676105"},{"key":"e_1_2_1_19_1","volume-title":"9th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT).","author":"Hassan Ahmed","year":"2014"},{"key":"e_1_2_1_20_1","volume-title":"Principles of Distributed Systems, Marcos K","author":"Hassan Ahmed"},{"key":"e_1_2_1_21_1","volume-title":"Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects. Technical Report CS-07-08","author":"Herlihy Maurice","year":"2007"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345237"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872048"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165164"},{"key":"e_1_2_1_25_1","unstructured":"Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming Revised Reprint. Elsevier.   Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming Revised Reprint. Elsevier."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1707801.1706304"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-015-0376-3"},{"key":"e_1_2_1_29_1","volume-title":"Retrieved","author":"Lawrence Livermore National Laboratory.","year":"2018"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03850-6_15"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066650.1066660"},{"key":"e_1_2_1_32_1","volume-title":"Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT).","author":"Marathe Virendra J."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111320.1111068"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564881"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1229428.1229442"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693462"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122971.1123001"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2076021.2048073"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050028"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301339"},{"key":"e_1_2_1_42_1","unstructured":"Alexander Spiegelman. 2016. Personal Communication. (October 2016).  Alexander Spiegelman. 2016. Personal Communication. (October 2016)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908112"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2419651"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688510"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209690","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209690","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209690","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:33Z","timestamp":1750210773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209690"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,31]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3209690"],"URL":"https:\/\/doi.org\/10.1145\/3209690","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,31]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}