{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:27Z","timestamp":1750306107177,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,9,11]],"date-time":"2017-09-11T00:00:00Z","timestamp":1505088000000},"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":[[2017,9,11]]},"abstract":"<jats:p>In this paper, we propose a method to implement any concurrent data structure. Our method produces implementations that work particularly well in non-uniform memory access (NUMA) machines. Due to recent architecture trends, highly concurrent servers today are NUMA machines, where the cost of accessing a memory location is not the same across every core. To fully leverage these machines, programmers need efficient concurrent data structures that are aware of the NUMA performance artifacts.We propose Node Replication (NR), a black-box approach to obtaining such data structures. NR takes an arbitrary sequential data structure and automatically transforms it into a NUMA-aware concurrent data structure satisfying linearizability. Using NR requires no expertise in concurrent data structure design, and the result is free of concurrency bugs. NR draws ideas from two disciplines: shared-memory algorithms and distributed systems. Briefly, NR implements a NUMA-aware shared log, and then uses the log to replicate data structures consistently across NUMA nodes. The cost of NR is additional memory for its log and replicas.<\/jats:p>","DOI":"10.1145\/3139645.3139650","type":"journal-article","created":{"date-parts":[[2017,9,12]],"date-time":"2017-09-12T18:56:39Z","timestamp":1505242599000},"page":"24-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["How to implement any concurrent data structure for modern servers"],"prefix":"10.1145","volume":"51","author":[{"given":"Irina","family":"Calciu","sequence":"first","affiliation":[{"name":"VMware Research"}]},{"given":"Siddhartha","family":"Sen","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]},{"given":"Mahesh","family":"Balakrishnan","sequence":"additional","affiliation":[{"name":"Yale University"}]},{"given":"Marcos K.","family":"Aguilera","sequence":"additional","affiliation":[{"name":"VMware Research"}]}],"member":"320","published-online":{"date-parts":[[2017,9,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/redis.io  http:\/\/redis.io"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535930"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629579"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/99163.99182"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/74850.74854"},{"key":"e_1_2_1_6_1","first-page":"43","volume-title":"Symposium on Operating Systems Design and Implementation","author":"Boyd-Wickizer S.","year":"2008","unstructured":"S. Boyd-Wickizer , H. Chen , R. Chen , Y. Mao , F. Kaashoek , R. Morris , A. Pesterev , L. Stein , M. Wu , Y. Dai , Y. Zhang , and Z. Zhang . Corey: an operating system for many cores . In Symposium on Operating Systems Design and Implementation , pages 43 -- 57 , Dec. 2008 . S. Boyd-Wickizer, H. Chen, R. Chen, Y. Mao, F. Kaashoek, R. Morris, A. Pesterev, L. Stein, M. Wu, Y. Dai, Y. Zhang, and Z. Zhang. Corey: an operating system for many cores. In Symposium on Operating Systems Design and Implementation, pages 43--57, Dec. 2008."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935796"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/265924.265930"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03850-6_7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442532"},{"key":"e_1_2_1_12_1","volume-title":"USENIX Workshop on Hot Topics in Parallelism","author":"Calciu I.","year":"2013","unstructured":"I. Calciu , J. E. Gottschlich , and M. Herlihy . Using delegation and elimination to implement a scalable NUMA-friendly stack . In USENIX Workshop on Hot Topics in Parallelism , June 2013 . I. Calciu, J. E. Gottschlich, and M. Herlihy. Using delegation and elimination to implement a scalable NUMA-friendly stack. In USENIX Workshop on Hot Topics in Parallelism, June 2013."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037721"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/74850.74855"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451157"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522714"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694359"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2663165.2663321"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989502"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145848"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145849"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"e_1_2_1_24_1","first-page":"87","volume-title":"Symposium on Operating Systems Design and Implementation","author":"Gamsa B.","year":"1999","unstructured":"B. Gamsa , O. Krieger , J. Appavoo , and M. Stumm . Tornado: Maximizing locality and concurrency in a shared memory multiprocessor operating system . In Symposium on Operating Systems Design and Implementation , pages 87 -- 100 , Feb. 1999 . B. Gamsa, O. Krieger, J. Appavoo, and M. Stumm. Tornado: Maximizing locality and concurrency in a shared memory multiprocessor operating system. In Symposium on Operating Systems Design and Implementation, pages 87--100, Feb. 1999."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851155"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810540"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810540"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.08.011"},{"key":"e_1_2_1_29_1","volume-title":"Workshop on Systems for Future Multicore Architectures","author":"Herlihy M.","year":"2011","unstructured":"M. Herlihy and I. Calciu . Work in progress: Shared nothing transactional memory . In Workshop on Systems for Future Multicore Architectures , Apr. 2011 . M. Herlihy and I. Calciu. Work in progress: Shared nothing transactional memory. In Workshop on Systems for Future Multicore Architectures, Apr. 2011."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/173682.165164"},{"key":"e_1_2_1_31_1","volume-title":"The Art of Multiprocessor Programming","author":"Herlihy M.","year":"2008","unstructured":"M. Herlihy and N. Shavit . The Art of Multiprocessor Programming . Morgan Kaufmann Publishers Inc ., San Francisco, CA, USA, 2008 . M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626299"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217935.1217949"},{"key":"e_1_2_1_35_1","first-page":"53","volume-title":"USENIX Annual Technical Conference","author":"Lachaize R.","year":"2012","unstructured":"R. Lachaize , B. Lepers , and V. Qu\u00e9ma . MemProf: A memory profiler for NUMA multicore systems . In USENIX Annual Technical Conference , pages 53 -- 64 , June 2012 . R. Lachaize, B. Lepers, and V. Qu\u00e9ma. MemProf: A memory profiler for NUMA multicore systems. In USENIX Annual Technical Conference, pages 53--64, June 2012."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_37_1","first-page":"429","volume-title":"Symposium on Networked Systems Design and Implementation","author":"Lim H.","year":"2014","unstructured":"H. Lim , D. Han , D. G. Andersen , and M. Kaminsky . MICA: A holistic approach to fast in-memory key-value storage . In Symposium on Networked Systems Design and Implementation , pages 429 -- 444 , Apr. 2014 . H. Lim, D. Han, D. G. Andersen, and M. Kaminsky. MICA: A holistic approach to fast in-memory key-value storage. In Symposium on Networked Systems Design and Implementation, pages 429--444, Apr. 2014."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2845079"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823285_84"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815406"},{"key":"e_1_2_1_42_1","first-page":"509","volume-title":"Parallel and Distributed Computing and Systems","author":"McKenney P. E.","year":"1998","unstructured":"P. E. McKenney and J. D. Slingwine . Read-copy-update: Using execution history to solve concurrency problems . In Parallel and Distributed Computing and Systems , pages 509 -- 518 , Oct. 1998 . P. E. McKenney and J. D. Slingwine. Read-copy-update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems, pages 509--518, Oct. 1998."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145874"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043560"},{"key":"e_1_2_1_45_1","volume-title":"Executing parallel programs with synchronization bottlenecks efficiently","author":"Oyama Y.","year":"1999","unstructured":"Y. Oyama , K. Taura , and A. Yonezawa . Executing parallel programs with synchronization bottlenecks efficiently , 1999 . Y. Oyama, K. Taura, and A. Yonezawa. Executing parallel programs with synchronization bottlenecks efficiently, 1999."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816692"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/822080.822810"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/98163.98167"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09873-9_45"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217935.1217965"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224987"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670994"},{"key":"e_1_2_1_54_1","volume-title":"Sept.","author":"Sutter H.","year":"2008","unstructured":"H. Sutter . Lock-free code : A false sense of security. Dr. Dobb's , Sept. 2008 . H. Sutter. Lock-free code: A false sense of security. Dr. Dobb's, Sept. 2008."},{"key":"e_1_2_1_55_1","volume-title":"Coping with parallelism. Technical report","author":"Treiber R. K.","year":"1986","unstructured":"R. K. Treiber . Systems programming : Coping with parallelism. Technical report , IBM Almaden Research Center , Apr. 1986 . R. K. Treiber. Systems programming: Coping with parallelism. Technical report, IBM Almaden Research Center, Apr. 1986."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237205"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442522"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851176"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3139645.3139650","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3139645.3139650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:39Z","timestamp":1750217439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3139645.3139650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,11]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9,11]]}},"alternative-id":["10.1145\/3139645.3139650"],"URL":"https:\/\/doi.org\/10.1145\/3139645.3139650","relation":{},"ISSN":["0163-5980"],"issn-type":[{"type":"print","value":"0163-5980"}],"subject":[],"published":{"date-parts":[[2017,9,11]]},"assertion":[{"value":"2017-09-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}