{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:43:07Z","timestamp":1767339787541,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,8,17]],"date-time":"2010-08-17T00:00:00Z","timestamp":1282003200000},"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":[[2010,8,17]]},"abstract":"<jats:p>This paper presents a novel concurrent hash table implementation which supports wait-free, near-linearly scalable lookup, even in the presence of concurrent modifications. In particular, this hash table implementation supports concurrent moves of hash table elements between buckets, for purposes such as renames.<\/jats:p>\n          <jats:p>Implementation of this algorithm in the Linux kernel demonstrates its performance and scalability. Benchmarks on a 64-way POWER system showed a 6x scalability improvement versus fine-grained locking, and a 1.5x improvement versus the current state of the art in Linux.<\/jats:p>\n          <jats:p>\n            To achieve these scalability improvements, the hash table implementation uses a new concurrent programming technique known as\n            <jats:italic>relativistic programming<\/jats:italic>\n            . This approach uses a copy-based update strategy to allow readers and writers to run concurrently without conflicts, avoiding many of the non-scalable costs of synchronization, inter-processor communication, and cache coherence. New techniques such as the proposed hash-table move algorithm allow readers to tolerate the resulting weak memory-ordering behavior that arises from allowing one version of a structure to be read concurrently with updates to a different version of the same structure. Relativistic programming techniques provide performance and scalability advantages over traditional synchronization, as demonstrated through several benchmarks.\n          <\/jats:p>","DOI":"10.1145\/1842733.1842750","type":"journal-article","created":{"date-parts":[[2010,8,19]],"date-time":"2010-08-19T13:12:46Z","timestamp":1282223566000},"page":"102-109","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Scalable concurrent hash tables via relativistic programming"],"prefix":"10.1145","volume":"44","author":[{"given":"Josh","family":"Triplett","sequence":"first","affiliation":[{"name":"Portland State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul E.","family":"McKenney","sequence":"additional","affiliation":[{"name":"IBM Linux Technology Center"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Walpole","sequence":"additional","affiliation":[{"name":"Portland State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,8,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065042"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454456.1454466"},{"key":"e_1_2_1_3_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. Introduction to Algorithms chapter Chapter 11: Hash Tables. MIT Press second edition 2001.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. Introduction to Algorithms chapter Chapter 11: Hash Tables. MIT Press second edition 2001."},{"key":"e_1_2_1_4_1","unstructured":"M. Desnoyers. Low-Impact Operating System Tracing. PhD thesis \u00c9cole Polytechnique Montr\u00e9al 2009.  M. Desnoyers. Low-Impact Operating System Tracing. PhD thesis \u00c9cole Polytechnique Montr\u00e9al 2009."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508263"},{"key":"e_1_2_1_6_1","unstructured":"Digital Equipment Corporation. Shared Memory Threads Interprocess Communication August 2001.  Digital Equipment Corporation. Shared Memory Threads Interprocess Communication August 2001."},{"key":"e_1_2_1_7_1","first-page":"28","author":"Fraser K.","year":"2004","journal-title":"University of Cambridge Computer Laboratory"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.472.0221"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.04.010"},{"volume-title":"Morgan Kaufmann Publishers","year":"2008","author":"Herlihy M.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","unstructured":"D. Knuth. The Art of Computer Programming chapter Section 6.4: Hashing. Addison-Wesley second edition 1998.  D. Knuth. The Art of Computer Programming chapter Section 6.4: Hashing. Addison-Wesley second edition 1998."},{"volume-title":"Gelato Conference","year":"2005","author":"Lameter C.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","first-page":"289","volume-title":"Ottawa Linux Symposium","author":"Linder H.","year":"2002"},{"key":"e_1_2_1_14_1","unstructured":"P. E. McKenney. Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System Kernels. PhD thesis OGI School of Science and Engineering at Oregon Health and Sciences University 2004.   P. E. McKenney. Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System Kernels. PhD thesis OGI School of Science and Engineering at Oregon Health and Sciences University 2004."},{"volume-title":"Adelaide","year":"2004","author":"McKenney P. E.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","first-page":"338","volume-title":"Ottawa Linux Symposium","author":"McKenney P. E.","year":"2002"},{"issue":"117","key":"e_1_2_1_17_1","article-title":"Scaling dcache with RCU","volume":"2004","author":"McKenney P. E.","year":"2004","journal-title":"Linux Journal"},{"key":"e_1_2_1_18_1","first-page":"509","volume-title":"Parallel and Distributed Computing and Systems","author":"McKenney P. E.","year":"1998"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.8"},{"key":"e_1_2_1_20_1","unstructured":"J. Morris. SELinux scalability and analysis patches November 2004. (accessed April 28 2008).  J. Morris. SELinux scalability and analysis patches November 2004. (accessed April 28 2008)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294271"},{"key":"e_1_2_1_22_1","unstructured":"J. Triplett. Lockless hash table lookups while performing key update on hash table element. US Patent 7668851 February 2010.  J. Triplett. Lockless hash table lookups while performing key update on hash table element. US Patent 7668851 February 2010."},{"volume-title":"3rd ACM SIGPLAN Workshop on Transactional Computing","year":"2008","author":"Volos H.","key":"e_1_2_1_23_1"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1842733.1842750","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1842733.1842750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:08:36Z","timestamp":1750248516000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1842733.1842750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,17]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,8,17]]}},"alternative-id":["10.1145\/1842733.1842750"],"URL":"https:\/\/doi.org\/10.1145\/1842733.1842750","relation":{},"ISSN":["0163-5980"],"issn-type":[{"type":"print","value":"0163-5980"}],"subject":[],"published":{"date-parts":[[2010,8,17]]},"assertion":[{"value":"2010-08-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}