{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:22Z","timestamp":1779174802213,"version":"3.51.4"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["621-2017-04812"],"award-info":[{"award-number":["621-2017-04812"]}],"id":[{"id":"10.13039\/501100004359","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":[[2021,6,30]]},"abstract":"<jats:p>Concurrent key-value stores with range query support are crucial for the scalability and performance of many applications. Existing lock-free data structures of this kind use a fixed synchronization granularity. Using a fixed synchronization granularity in a concurrent key-value store with range query support is problematic as the best performing synchronization granularity depends on a number of factors that are difficult to predict, such as the level of contention and the number of items that are accessed by range queries. We present the first linearizable lock-free key-value store with range query support that dynamically adapts its synchronization granularity. This data structure is called the lock-free contention adapting search tree (LFCA tree). An LFCA tree automatically performs local adaptations of its synchronization granularity based on heuristics that take contention and the performance of range queries into account. We show that the operations of LFCA trees are linearizable, that the lookup operation is wait-free, and that the remaining operations (insert, remove and range query) are lock-free. Our experimental evaluation shows that LFCA trees achieve more than twice the throughput of related lock-free data structures in many scenarios. Furthermore, LFCA trees are able to perform substantially better than data structures with a fixed synchronization granularity over a wide range of scenarios due to their ability to adapt to the scenario at hand.<\/jats:p>","DOI":"10.1145\/3460874","type":"journal-article","created":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T11:36:13Z","timestamp":1626953773000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Lock-free Contention Adapting Search Trees"],"prefix":"10.1145","volume":"8","author":[{"given":"Kjell","family":"Winblad","sequence":"first","affiliation":[{"name":"Ericsson AB, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Sagonas","sequence":"additional","affiliation":[{"name":"Uppsala University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bengt","family":"Jonsson","sequence":"additional","affiliation":[{"name":"Uppsala University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Archita Agarwal Zhiyu Liu Eli Rosenthal and Vikram Saraph. 2017. Linearizable Iterators for Concurrent Sets. arXiv:1705.08885. Retrieved from https:\/\/arxiv.org\/abs\/1705.088  Archita Agarwal Zhiyu Liu Eli Rosenthal and Vikram Saraph. 2017. Linearizable Iterators for Concurrent Sets. arXiv:1705.08885. Retrieved from https:\/\/arxiv.org\/abs\/1705.088"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178489"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484254"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018761"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693488"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35476-2_3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25873-2_15"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767436"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3007748.3007771"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3122955.3122973"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835736"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323197"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.01.011"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/99163.99185"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784734"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511530104"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2642937.2642995"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_16"},{"key":"e_1_2_1_21_1","volume-title":"Implementing Contention-Friendly Range Queries in Non-Blocking Key-Value Stores. Bachelor Thesis","author":"Robertson Callum","unstructured":"Callum Robertson . 2014. Implementing Contention-Friendly Range Queries in Non-Blocking Key-Value Stores. Bachelor Thesis . The University of Sydney . Callum Robertson. 2014. Implementing Contention-Friendly Range Queries in Non-Blocking Key-Value Stores. Bachelor Thesis. The University of Sydney."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2017.11.007"},{"key":"e_1_2_1_23_1","unstructured":"Konstantinos Sagonas and Kjell Winblad. 2018. Contention Adapting Search Trees. Retrieved from http:\/\/www.it.uu.se\/research\/group\/languages\/software\/ca_tree.  Konstantinos Sagonas and Kjell Winblad. 2018. Contention Adapting Search Trees. Retrieved from http:\/\/www.it.uu.se\/research\/group\/languages\/software\/ca_tree."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2013.43"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536232"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.ICCSW.2017.7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210413"},{"key":"e_1_2_1_29_1","volume-title":"Retrieved","author":"Network Developer","year":"2017","unstructured":"Yahoo! Developer Network . 2017 . Flurry Analytics . Retrieved July 26, 2017 from https:\/\/developer.yahoo.com\/flurry\/docs\/analytics\/. Yahoo! Developer Network. 2017. Flurry Analytics. Retrieved July 26, 2017 from https:\/\/developer.yahoo.com\/flurry\/docs\/analytics\/."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460874","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460874","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:29Z","timestamp":1750195469000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3460874"],"URL":"https:\/\/doi.org\/10.1145\/3460874","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}