{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T00:46:04Z","timestamp":1759365964401,"version":"build-2065373602"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,10,13]]},"DOI":"10.1145\/3731569.3764807","type":"proceedings-article","created":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T12:43:24Z","timestamp":1759322604000},"page":"1131-1148","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Scalable Address Spaces using Concurrent Interval Skiplist"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4257-5294","authenticated-orcid":false,"given":"Tae Woo","family":"Kim","sequence":"first","affiliation":[{"name":"KAIST, Daejeon, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5602-2397","authenticated-orcid":false,"given":"Youngjin","family":"Kwon","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2115-0871","authenticated-orcid":false,"given":"Jeehoon","family":"Kang","sequence":"additional","affiliation":[{"name":"KAIST \/ FuriosaAI, Seoul, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,12]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"263","article-title":"An algorithm for the organization of information","volume":"146","author":"Adelson-Velsky Georgy M","year":"1962","unstructured":"Georgy M Adelson-Velsky and Evgenii Mikhailovich Landis. 1962. An algorithm for the organization of information. In Proceedings of the USSR Academy of Sciences, Vol. 146. 263\u2013266.","journal-title":"Proceedings of the USSR Academy of Sciences"},{"key":"e_1_3_2_1_2_1","unstructured":"Apache. 2025. Apache HTTP server project. https:\/\/httpd.apache.org"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 12th European Conference on Computer Systems","author":"Balmau Oana","year":"2017","unstructured":"Oana Balmau, Rachid Guerraoui, Vasileios Trigonakis, and Igor Zablotchi. 2017. FloDB: Unlocking memory in persistent key-value stores. In Proceedings of the 12th European Conference on Computer Systems (Belgrade, Serbia) (EuroSys '17). Association for Computing Machinery, New York, NY, USA, 80\u201394. 10.1145\/3064176.3064193"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles","author":"Baumann Andrew","year":"2009","unstructured":"Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Sch\u00fcpbach, and Akhilesh Singhania. 2009. The Multikernel: A new OS architecture for scalable multicore systems. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (Big Sky, Montana, USA) (SOSP '09). Association for Computing Machinery, New York, NY, USA, 29\u201344. 10.1145\/1629575.1629579"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control","author":"Bayer R.","unstructured":"R. Bayer and E. McCreight. 1970. Organization and maintenance of large ordered indices. In Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control (Houston, Texas) (SIGFIDET '70). Association for Computing Machinery, New York, NY, USA, 107\u2013141. 10.1145\/1734663.1734671"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Berger Emery D.","unstructured":"Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson. 2000. Hoard: A scalable memory allocator for multithreaded applications. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (Cambridge, Massachusetts, USA) (ASPLOS IX). Association for Computing Machinery, New York, NY, USA, 117\u2013128. 10.1145\/378993.379232"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques","author":"Bienia Christian","year":"2008","unstructured":"Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, and Kai Li. 2008. The PARSEC benchmark suite: Characterization and architectural implications. In Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques (Toronto, Ontario, Canada) (PACT '08). Association for Computing Machinery, New York, NY, USA, 72\u201381. 10.1145\/1454115.1454128"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 5th Annual Workshop on Modeling, Benchmarking and Simulation (MoBS). 1\u20139.","author":"Bienia Christian","year":"2009","unstructured":"Christian Bienia and Kai Li. 2009. PARSEC 2.0: A new benchmark suite for chip-multiprocessors. In Proceedings of the 5th Annual Workshop on Modeling, Benchmarking and Simulation (MoBS). 1\u20139."},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08)","author":"Boyd-Wickizer Silas","year":"2008","unstructured":"Silas Boyd-Wickizer, Haibo Chen, Rong Chen, Yandong Mao, Frans Kaashoek, Robert Morris, Aleksey Pesterev, Lex Stein, Ming Wu, Yuehua Dai, Yang Zhang, and Zheng Zhang. 2008. Corey: An operating system for many cores. In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08). USENIX Association, San Diego, CA, 43\u201357. https:\/\/www.usenix.org\/conference\/osdi-08\/corey-operating-system-many-cores"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 10)","author":"Boyd-Wickizer Silas","year":"2010","unstructured":"Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich. 2010. An analysis of Linux scalability to many cores. In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI 10). USENIX Association, Vancouver, BC, 1\u201316. https:\/\/www.usenix.org\/conference\/osdi10\/analysis-linux-scalability-many-cores"},{"key":"e_1_3_2_1_11_1","unstructured":"Davidlohr Bueso. 2018. mm: Towards parallel address space operations. https:\/\/lwn.net\/Articles\/746537"},{"key":"e_1_3_2_1_12_1","unstructured":"Elasticsearch B.V. 2025. Elasticsearch. https:\/\/www.elastic.co\/elasticsearch"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Clements Austin T.","year":"2012","unstructured":"Austin T. Clements, M. Frans Kaashoek, and Nickolai Zeldovich. 2012. Scalable address spaces using RCU balanced trees. In Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems (London, England, UK) (ASPLOS XVII). Association for Computing Machinery, New York, NY, USA, 199\u2013210. 10.1145\/2150976.2150998"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 8th ACM European Conference on Computer Systems (Prague, Czech Republic) (EuroSys '13)","author":"Clements Austin T.","year":"2013","unstructured":"Austin T. Clements, M. Frans Kaashoek, and Nickolai Zeldovich. 2013. RadixVM: Scalable address spaces for multithreaded applications. In Proceedings of the 8th ACM European Conference on Computer Systems (Prague, Czech Republic) (EuroSys '13). Association for Computing Machinery, New York, NY, USA, 211\u2013224. 10.1145\/2465351.2465373"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699681"},{"key":"e_1_3_2_1_16_1","unstructured":"Jonathan Corbet. 2010. Big reader locks. https:\/\/lwn.net\/Articles\/378911"},{"key":"e_1_3_2_1_17_1","unstructured":"Jonathan Corbet. 2017. Range reader\/writer locks for the kernel. https:\/\/lwn.net\/Articles\/724502"},{"key":"e_1_3_2_1_18_1","unstructured":"Jonathan Corbet. 2019. How to get rid of mmap_sem. https:\/\/lwn.net\/Articles\/787629"},{"key":"e_1_3_2_1_19_1","unstructured":"Jonathan Corbet. 2022. Concurrent page-fault handling with per-VMA locks. https:\/\/lwn.net\/Articles\/906852"},{"key":"e_1_3_2_1_20_1","volume-title":"McKenney","author":"Desnoyers Mathieu","year":"2025","unstructured":"Mathieu Desnoyers and Paul E. McKenney. 2025. Userspace RCU. https:\/\/liburcu.org"},{"key":"e_1_3_2_1_21_1","unstructured":"Laurent Dufour. 2017. Speculative page faults. https:\/\/lwn.net\/Articles\/725607"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the BSDCan Conference","author":"Evans Jason","year":"2006","unstructured":"Jason Evans. 2006. A scalable concurrent malloc (3) implementation for FreeBSD. In Proceedings of the BSDCan Conference (Ottawa, Canada). 1\u201314."},{"key":"e_1_3_2_1_23_1","unstructured":"Linux Foundation. 2025. drivers\/gpu\/drm\/drm_mm.c. https:\/\/git.kernel.org\/pub\/scm\/linux\/kernel\/git\/torvalds\/linux.git\/tree\/drivers\/gpu\/drm\/drm_mm.c"},{"key":"e_1_3_2_1_24_1","unstructured":"Linux Foundation. 2025. drivers\/gpu\/drm\/nouveau\/nouveau_uvmm.c. https:\/\/git.kernel.org\/pub\/scm\/linux\/kernel\/git\/torvalds\/linux.git\/tree\/drivers\/gpu\/drm\/nouveau\/nouveau_uvmm.c"},{"key":"e_1_3_2_1_25_1","unstructured":"Linux Foundation. 2025. fs\/xfs\/scrub\/bitmap.c. https:\/\/git.kernel.org\/pub\/scm\/linux\/kernel\/git\/torvalds\/linux.git\/tree\/fs\/xfs\/scrub\/bitmap.c"},{"key":"e_1_3_2_1_26_1","unstructured":"Linux Foundation. 2025. kernel\/bpf\/range_tree.c. https:\/\/git.kernel.org\/pub\/scm\/linux\/kernel\/git\/torvalds\/linux.git\/tree\/kernel\/bpf\/range_tree.c"},{"key":"e_1_3_2_1_27_1","unstructured":"Linux Foundation. 2025. Lock statistics. https:\/\/docs.kernel.org\/locking\/lockstat.html"},{"key":"e_1_3_2_1_28_1","unstructured":"Linux Foundation. 2025. Sequence counters and sequential locks. https:\/\/docs.kernel.org\/locking\/seqlock.html"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI 99)","author":"Gamsa Ben","year":"1999","unstructured":"Ben Gamsa, Orran Krieger, Jonathan Appavoo, and Michael Stumm. 1999. Tornado: Maximizing locality and concurrency in a shared memory multiprocessor operating system. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI 99). USENIX Association, New Orleans, LA, 87\u2013100. https:\/\/www.usenix.org\/conference\/osdi-99\/tornado-maximizing-locality-and-concurrency-shared-memory-multiprocessor"},{"key":"e_1_3_2_1_30_1","unstructured":"Sanjay Ghemawat and Jeff Dean. 2025. LevelDB. https:\/\/github.com\/google\/leveldb"},{"key":"e_1_3_2_1_31_1","unstructured":"Sanjay Ghemawat and Paul Menage. 2005. TCMalloc: Thread-caching malloc. https:\/\/goog-perftools.sourceforge.net\/doc\/tcmalloc.html"},{"key":"e_1_3_2_1_32_1","unstructured":"Will Glozer. 2025. Wrk - a HTTP benchmarking tool. https:\/\/github.com\/wg\/wrk"},{"key":"e_1_3_2_1_33_1","unstructured":"GNU. 2025. GNU C library. https:\/\/www.gnu.org\/software\/libc"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 19th Annual Symposium on Foundations of Computer Science (SFCS '78)","author":"Leo","year":"1978","unstructured":"Leo J. Guibas and Robert Sedgewick. 1978. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (SFCS '78). IEEE Computer Society, USA, 8\u201321. 10.1109\/SFCS.1978.3"},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings of the 15th International Conference on Distributed Computing (DISC '01)","author":"Harris Timothy L.","year":"2001","unstructured":"Timothy L. Harris. 2001. A pragmatic implementation of non-blocking linked-lists. In Proceedings of the 15th International Conference on Distributed Computing (DISC '01). Springer-Verlag, Berlin, Heidelberg, 300\u2013314."},{"key":"e_1_3_2_1_36_1","unstructured":"Liam R. Howlett. 2025. Maple tree. https:\/\/docs.kernel.org\/core-api\/maple_tree.html"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 10th ACM SIGOPS Asia-Pacific Workshop on Systems","author":"Kim June-Hyung","year":"2019","unstructured":"June-Hyung Kim, Jangwoong Kim, Hyeongu Kang, Chang-Gyu Lee, Sungyong Park, and Youngjae Kim. 2019. pNOVA: Optimizing shared file I\/O operations of NVM file system on manycore servers. In Proceedings of the 10th ACM SIGOPS Asia-Pacific Workshop on Systems (Hangzhou, China) (APSys '19). Association for Computing Machinery, New York, NY, USA, 1\u20137. 10.1145\/3343737.3343748"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 15th European Conference on Computer Systems","author":"Kogan Alex","year":"2020","unstructured":"Alex Kogan, Dave Dice, and Shady Issa. 2020. Scalable range locks for scalable address spaces and beyond. In Proceedings of the 15th European Conference on Computer Systems (Heraklion, Greece) (EuroSys '20). Association for Computing Machinery, New York, NY, USA, 1\u201315. 10.1145\/3342195.3387533"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 1st ACM SIGOPS\/EuroSys European Conference on Computer Systems 2006","author":"Krieger Orran","year":"2006","unstructured":"Orran Krieger, Marc Auslander, Bryan Rosenburg, Robert W. Wisniewski, Jimi Xenidis, Dilma Da Silva, Michal Ostrowski, Jonathan Appavoo, Maria Butrico, Mark Mergen, Amos Waterland, and Volkmar Uhlig. 2006. K42: Building a complete operating system. In Proceedings of the 1st ACM SIGOPS\/EuroSys European Conference on Computer Systems 2006 (Leuven, Belgium) (EuroSys '06). Association for Computing Machinery, New York, NY, USA, 133\u2013145. 10.1145\/1217935.1217949"},{"key":"e_1_3_2_1_40_1","volume-title":"Proceedings of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Kumar Mohan Kumar","year":"2018","unstructured":"Mohan Kumar Kumar, Steffen Maass, Sanidhya Kashyap, J\u00e1n Vesel\u00fd, Zi Yan, Taesoo Kim, Abhishek Bhattacharjee, and Tushar Krishna. 2018. LATR: Lazy translation coherence. In Proceedings of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems (Williamsburg, VA, USA) (ASPLOS '18). Association for Computing Machinery, New York, NY, USA, 651\u2013664. 10.1145\/3173162.3173198"},{"key":"e_1_3_2_1_41_1","unstructured":"Michel Lespinasse. 2020. [RFC 00\/24] Fine grained MM locking. https:\/\/patchwork.kernel.org\/project\/linux-mm\/cover\/20200224203057.162467-1-walken@google.com"},{"key":"e_1_3_2_1_42_1","unstructured":"Michel Lespinasse. 2021. Speculative page faults. https:\/\/lwn.net\/Articles\/851853"},{"key":"e_1_3_2_1_43_1","unstructured":"Michel Lespinasse. 2025. Linux. https:\/\/github.com\/lespinasse\/linux"},{"key":"e_1_3_2_1_44_1","volume-title":"Joseph M. Hellerstein, M. Frans Kaashoek","author":"Li Jinyang","year":"2003","unstructured":"Jinyang Li, Boon Thau Loo, Joseph M. Hellerstein, M. Frans Kaashoek, David R. Karger, and Robert Morris. 2003. On the Feasibility of Peer-to-Peer Web Indexing and Search. In Peer-to-Peer Systems II, M. Frans Kaashoek and Ion Stoica (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 207\u2013215."},{"key":"e_1_3_2_1_45_1","unstructured":"Yandong Mao Robert Morris and Frans Kaashoek. 2010. Optimizing MapReduce for multicore architectures. Technical Report MIT-CSAIL-TR-2010-020. MIT CSAIL."},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the USENIX 1996 Annual Technical Conference (USENIX ATC 96)","author":"McVoy Larry","year":"1996","unstructured":"Larry McVoy and Carl Staelin. 1996. lmbench: Portable tools for performance analysis. In Proceedings of the USENIX 1996 Annual Technical Conference (USENIX ATC 96). USENIX Association, San Diego, CA, 1\u201317. https:\/\/www.usenix.org\/conference\/usenix-1996-annual-technical-conference\/lmbench-portable-tools-performance-analysis"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC 16)","author":"Min Changwoo","year":"2016","unstructured":"Changwoo Min, Sanidhya Kashyap, Steffen Maass, and Taesoo Kim. 2016. Understanding manycore scalability of file systems. In Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC 16). USENIX Association, Denver, CO, 71\u201385. https:\/\/www.usenix.org\/conference\/atc16\/technical-sessions\/presentation\/min"},{"key":"e_1_3_2_1_48_1","unstructured":"MongoDB. 2025. MongoDB. https:\/\/www.mongodb.com"},{"key":"e_1_3_2_1_49_1","unstructured":"Nir N Shavit Yosef Lev and Maurice P Herlihy. 2011. Concurrent Lockfree Skiplist with Wait-free Contains Operator. https:\/\/patentcenter.uspto.gov\/applications\/12191008 US Patent 7 937 378."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_3_2_1_51_1","volume-title":"Proceedings of the 3rd Symposium on Networked Systems Design & Implementation (NSDI 06)","author":"Stribling Jeremy","unstructured":"Jeremy Stribling, Jinyang Li, and Isaac G. Councill. 2006. OverCite: A distributed, cooperative CiteSeer. In Proceedings of the 3rd Symposium on Networked Systems Design & Implementation (NSDI 06). USENIX Association, San Jose, CA, 143\u2013153. https:\/\/www.usenix.org\/conference\/nsdi-06\/overcite-distributed-cooperative-citeseer"},{"key":"e_1_3_2_1_52_1","unstructured":"Linux test project. 2025. Linux test project. https:\/\/github.com\/linux-test-project\/ltp"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278901.1278909"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531793.1531805"},{"key":"e_1_3_2_1_55_1","volume-title":"Windows Internals: System Architecture, Processes, Threads, Memory Management, and More, Part 1","author":"Yosifovich Pavel","year":"2017","unstructured":"Pavel Yosifovich, Alex Ionescu, Mark E Russinovich, and David A Solomon. 2017. Windows Internals: System Architecture, Processes, Threads, Memory Management, and More, Part 1. Microsoft Press."},{"key":"e_1_3_2_1_56_1","unstructured":"Qi Zheng. 2022. [RFC PATCH 00\/18] Try to free user PTE page table pages. https:\/\/lwn.net\/ml\/linux-kernel\/20220429133552.33768-1-zhengqi.arch@bytedance.com"},{"key":"e_1_3_2_1_57_1","unstructured":"Peter Zijlstra. 2014. Another go at speculative page faults. https:\/\/lwn.net\/Articles\/617344"}],"event":{"name":"SOSP '25: ACM SIGOPS 31st Symposium on Operating Systems Principles","location":"Lotte Hotel World Seoul Republic of Korea","acronym":"SOSP '25","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","USENIX"]},"container-title":["Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles"],"original-title":[],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T12:48:32Z","timestamp":1759322912000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731569.3764807"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,12]]},"references-count":57,"alternative-id":["10.1145\/3731569.3764807","10.1145\/3731569"],"URL":"https:\/\/doi.org\/10.1145\/3731569.3764807","relation":{},"subject":[],"published":{"date-parts":[[2025,10,12]]},"assertion":[{"value":"2025-10-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}