Unexpected scaling in path copying trees

thesis Unexpected scaling in path copying trees published yes Vitaly Aksenov author Trevor A Brown author 3569F0A0-F248-11E8-B48F-1D18A9856A87 Alexander Fedorov author 2e711909-896a-11ed-bdf8-eb0f5a2984c6 Ilya Kokorin author DaAl department GradSch department PPoPP: Sympopsium on Principles and Practice of Parallel Programming Although a wide variety of handcrafted concurrent data structures have been proposed, there is considerable interest in universal approaches (Universal Constructions or UCs) for building concurrent data structures. UCs (semi-)automatically convert a sequential data structure into a concurrent one. The simplest approach uses locks [3, 6] that protect a sequential data structure and allow only one process to access it at a time. However, the resulting data structure is blocking. Most work on UCs instead focuses on obtaining non-blocking progress guarantees such as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et al. Association for Computing Machinery2023Montreal, QB, Canada eng Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming 979840070015610.1145/3572848.3577512 438-440 V. Aksenov, T. A. Brown, A. Fedorov, and I. Kokorin, Unexpected scaling in path copying trees. Association for Computing Machinery, 2023, pp. 438–440. Aksenov, V., Brown, T. A., Fedorov, A., & Kokorin, I. (2023). Unexpected scaling in path copying trees. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp. 438–440). Montreal, QB, Canada: Association for Computing Machinery. <a href="https://doi.org/10.1145/3572848.3577512">https://doi.org/10.1145/3572848.3577512</a> Aksenov V, Brown TA, Fedorov A, Kokorin I. Unexpected Scaling in Path Copying Trees. Association for Computing Machinery; 2023:438-440. doi:<a href="https://doi.org/10.1145/3572848.3577512">10.1145/3572848.3577512</a> Aksenov, Vitaly, et al. “Unexpected Scaling in Path Copying Trees.” Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2023, pp. 438–40, doi:<a href="https://doi.org/10.1145/3572848.3577512">10.1145/3572848.3577512</a>. Aksenov, Vitaly, Trevor A Brown, Alexander Fedorov, and Ilya Kokorin. Unexpected Scaling in Path Copying Trees. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery, 2023. <a href="https://doi.org/10.1145/3572848.3577512">https://doi.org/10.1145/3572848.3577512</a>. V. Aksenov, T.A. Brown, A. Fedorov, I. Kokorin, Unexpected Scaling in Path Copying Trees, Association for Computing Machinery, 2023. Aksenov V, Brown TA, Fedorov A, Kokorin I. 2023. Unexpected scaling in path copying trees, Association for Computing Machinery,p. 127362023-03-19T23:00:58Z2026-06-18T17:29:03Z