{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:21:40Z","timestamp":1759134100879,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,6,29]],"date-time":"2015-06-29T00:00:00Z","timestamp":1435536000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"GreenTM FCT Project","award":["EXPL\/EEI-ESS\/0361\/2013"],"award-info":[{"award-number":["EXPL\/EEI-ESS\/0361\/2013"]}]},{"name":"specSTM FCT Project","award":["PTDC\/EIA-EIA\/122785\/2010"],"award-info":[{"award-number":["PTDC\/EIA-EIA\/122785\/2010"]}]},{"name":"Fundacao para a Ciencia e Tecnologia","award":["UID\/CEC\/50021\/2013"],"award-info":[{"award-number":["UID\/CEC\/50021\/2013"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2015,7,8]]},"abstract":"<jats:p>The multicore revolution that took place one decade ago has turned parallel programming into a major concern for the mainstream software development industry. In this context, Transactional Memory (TM) has emerged as a simpler and attractive alternative to that of lock-based synchronization, whose complexity and error-proneness are widely recognized.<\/jats:p>\n          <jats:p>The notion of permissiveness in TM translates to only aborting a transaction when it cannot be accepted in any history that guarantees a target correctness criterion. This theoretically powerful property is often neglected by state-of-the-art TMs because it imposes considerable algorithmic costs. Instead, these TMs opt to maximize their implementation\u2019s efficiency by aborting transactions under overly conservative conditions. As a result, they risk rejecting a significant number of safe executions.<\/jats:p>\n          <jats:p>\n            In this article, we seek to identify a sweet spot between permissiveness and efficiency by introducing the Time-Warp Multiversion (TWM) algorithm. TWM is based on the key idea of allowing an update transaction that has performed stale reads (i.e., missed the writes of concurrently committed transactions) to be serialized by \u201ccommitting it in the past,\u201d which we call a\n            <jats:italic>time-warp<\/jats:italic>\n            commit. At its core, TWM uses a novel, lightweight validation mechanism with little computational overhead. TWM also guarantees that read-only transactions can never be aborted. Further, TWM guarantees\n            <jats:italic>Virtual World Consistency<\/jats:italic>\n            , a safety property that is deemed as particularly relevant in the context of TM.\n          <\/jats:p>\n          <jats:p>We demonstrate the practicality of this approach through an extensive experimental study: we compare TWM with five other TMs, representative of typical alternative design choices, and on a wide variety of benchmarks. This study shows an average performance improvement across all considered workloads and TMs of 65% in high concurrency scenarios, with gains extending up to 9 \u00d7 with the most favorable benchmarks. These results are a consequence of TWM\u2019s ability to achieve drastic reduction of aborts in scenarios of nonminimal contention, while introducing little overhead (approximately 10%) in worst-case, synthetically designed scenarios (i.e., no contention or contention patterns that cannot be optimized using TWM).<\/jats:p>","DOI":"10.1145\/2775435","type":"journal-article","created":{"date-parts":[[2015,6,29]],"date-time":"2015-06-29T18:10:42Z","timestamp":1435601442000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Time-Warp"],"prefix":"10.1145","volume":"2","author":[{"given":"Nuno","family":"Diegues","sequence":"first","affiliation":[{"name":"INESC-ID\/Instituto Superior T\u00e9cnico, University of Lisbon, Portugal"}]},{"given":"Paolo","family":"Romano","sequence":"additional","affiliation":[{"name":"INESC-ID\/Instituto Superior T\u00e9cnico, University of Lisbon, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2015,6,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1504176.1504203"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1946143.1946151"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.287"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223785"},{"volume-title":"Concurrency Control and Recovery in Database Systems","author":"Bernstein Philip A.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376690"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2013.6575311"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2075416.2075439"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950373"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693464"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168900"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_14"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_11"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2013.27"},{"volume-title":"Proceedings of the 11th International Conference on Autonomic Computing (ICAC\u201914)","year":"2014","author":"Diegues Nuno","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628080"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1924421.1924440"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2010.49"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345241"},{"volume-title":"Proceedings of the Workshop on Programmability Issues for Multi-Core Computers (MULTIPROG).","year":"2010","author":"Felber Pascal","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1941553.1941579"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626410000041"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_21"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_23"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345233"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273029"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345237"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/850929.851942"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165164"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.04.037"},{"key":"e_1_2_1_33_1","unstructured":"Intel Corporation. February 2012. Intel architecture instruction set extensions programming reference. In 319433-012 edition.  Intel Corporation. February 2012. Intel architecture instruction set extensions programming reference. In 319433-012 edition."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3916.3988"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584013"},{"volume-title":"Proceedings of the Workshop on Transactional Computing (TRANSACT\u201907)","year":"2007","author":"Lev Yossi","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541952"},{"volume-title":"Proceedings of the 27th Symposium on Distributed Computing (DISC\u201913)","author":"Lu Li","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2008.69"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486188"},{"volume-title":"Proceedings of the Symposium on Workload Characterization (IISWC\u201908)","author":"Minh Chi Cao","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989500"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2075029.2075041"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835704"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1504176.1504201"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370816.2370836"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2086696.2086733"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503232"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2775435","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2775435","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:27Z","timestamp":1750223247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2775435"}},"subtitle":["Efficient Abort Reduction in Transactional Memory"],"short-title":[],"issued":{"date-parts":[[2015,6,29]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,7,8]]}},"alternative-id":["10.1145\/2775435"],"URL":"https:\/\/doi.org\/10.1145\/2775435","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2015,6,29]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}