Fixing Non-blocking Data Structures for Better Compatibility with Memory Reclamation Schemes
Abstract
We present a new technique, Safe Concurrent Optimistic Traversals (SCOT), to address a well-known problem related to optimistic traversals with classical and more recent safe memory reclamation (SMR) schemes, such as Hazard Pointers (HP), Hazard Eras (HE), Interval-Based Reclamation (IBR), and Hyaline. Unlike Epoch-Based Reclamation (EBR), these (robust) schemes protect against stalled threads but lack support for well-known data structures with optimistic traversals, e.g., Harris' list and the Natarajan-Mittal tree. Such schemes are either incompatible with them or need changes with performance trade-offs (e.g., the Harris-Michael list).
Fields of Study & Subjects
Security and Verification in Computing
Distributed systems and fault tolerance
Radiation Effects in Electronics
Publication details
- Journal / source
- Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming
- Publisher
- ACM
- Pages
- 26–39
- Publication date
- 28 January 2026
- Language
- EN