Duc-Than Nguyen

A list of high-performance, mostly non-blocking data structures.

1. Treiber's Stack R. Kent Treiber. 1986. Systems programming: coping with parallelism. (https://dominoweb.draco.res.ibm.com/reports/rj5118.pdf)
2. Michael&Scott's Queue Maged M. Michael and Michael L. Scott. 1996. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. (https://doi.org/10.1145/248052.248106)
3. DGLM Queue Simon Doherty, Lindsay Groves, Victor Luchangco, and Mark Moir. 2004. Formal Verification of a Practical Lock-Free Queue Algorithm. (https://doi.org/10.1007/978-3-540-30232-2_7)
4. Vechev&Yahav's DCAS Set Martin T. Vechev and Eran Yahav. 2008. Deriving linearizable fine-grained concurrent objects. (Figures 8 and 9.) (https://doi.org/10.1145/1375581.1375598)
5. Vechev&Yahav's CAS Set Martin T. Vechev and Eran Yahav. 2008. Deriving linearizable fine-grained concurrent objects. (Figures 2.) (https://doi.org/10.1145/1375581.1375598)
6. ORVVY Set Peter W. O'Hearn, Noam Rinetzky, Martin T. Vechev, Eran Yahav, and Greta Yorsh. 2010. Verifying linearizability with hindsight. (https://doi.org/10.1145/1835698.1835722)
7. Michael's Set Maged M. Michael. 2002. High performance dynamic lock-free hash tables and list-based sets. (https://doi.org/10.1145/564870.564881)
8. Harris' List (Set) Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. (https://doi.org/10.1007/3-540-45414-4_21)
9. Elimination-backoff Stacks
   • Danny Hendler, Nir Shavit, and Lena Yerushalmi. 2004. A scalable lock-free stack algorithm. (https://doi.org/10.1145/1007912.1007944)
   • Gal Bar-Nissan, Danny Hendler, and Adi Suissa. 2011. A Dynamic Elimination-Combining Stack Algorithm. (https://doi.org/10.1007/978-3-642-25873-2_37)
10. More (Optimized) Queues
    • Philippas Tsigas and Yi Zhang. 2001. A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems. (https://doi.org/10.1145/378580.378611)
    • Alex Kogan and Erez Petrank. 2011. Wait-free queues with multiple enqueuers and dequeuers. (https://doi.org/10.1145/1941553.1941585)
    • Alex Kogan and Erez Petrank. 2012. A methodology for creating fast wait-free data structures. (https://doi.org/10.1145/2145816.2145835)
    • Adam Morrison and Yehuda Afek. 2013. (https://doi.org/10.1145/2442516.2442527)
11. Time-stamped Stacks and Queues Stack Mike Dodds, Andreas Haas, and Christoph M. Kirsch. 2015. A Scalable, Correct Time-Stamped Stack. (https://doi.org/10.1145/2676726.2676963)
12. Priority Queues
    • Greg Barnes. 1992. Wait-Free Algorithms for Heaps. (https://dada.cs.washington.edu/research/tr/1994/12/UW-CSE-94-12-07.pdf)
    • Amos Israeli and Lihu Rappoport. 1993. Efficient Wait-Free Implementation of a Concurrent Priority Queue. (https://doi.org/10.1007/3-540-57271-6_23)
    • Håkan Sundell and Philippas Tsigas. 2003. Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems. (https://doi.org/10.1109/IPDPS.2003.1213189)
13. Skip Lists
    • Håkan Sundell and Philippas Tsigas. 2003. Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems. (https://doi.org/10.1109/IPDPS.2003.1213189)
    • Keir Fraser. 2004. Practical lock-freedom. (http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.599193)
    • Mikhail Fomitchev and Eric Ruppert. 2004. Lock-free linked lists and skip lists. (https://doi.org/10.1145/1011767.1011776)
14. Doubly-linked and double-ended queues
    • Michael Greenwald. 1990. Non-Blocking Synchronization and System Design. (http://i.stanford.edu/pub/cstr/reports/cs/tr/99/1624/CS-TR-99-1624.pdf)
    • Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton. 1998. Thread Scheduling for Multiprogrammed Multiprocessors. (https://doi.org/10.1145/277651.277678)
    • Ole Agesen, David Detlefs, Christine H. Flood, Alex Garthwaite, Paul Alan Martin, Nir Shavit, and Guy L. Steele Jr. 2000. DCAS-based concurrent deques. (https://doi.org/10.1145/341800.341817)
    • Maged M. Michael. 2003. CAS-Based Lock-Free Algorithm for Shared Deques. (https://doi.org/10.1007/978-3-540-45209-6_92)
    • Håkan Sundell, Philippas Tsigas. 2004. Lock-Free and Practical Doubly Linked List-Based Deques Using Single-Word Compare-and-Swap. (https://doi.org/10.1007/11516798_18)
    • Niloufar Shafiei. 2015. Non-Blocking Doubly-Linked Lists with Good Amortized Complexity. (https://doi.org/10.4230/LIPIcs.OPODIS.2015.35)
    • Andreas Haas. 2015. Fast Concurrent Data Structures Through Timestamping. (http://www.cs.uni-salzburg.at/~ahaas/papers/thesis.pdf)
15. Search Trees
    • Greg Barnes. 1992. Wait-Free Algorithms for Heaps. (https://dada.cs.washington.edu/research/tr/1994/12/UW-CSE-94-12-07.pdf)
    • Anastasia Braginsky and Erez Petrank. 2012. A lock-free B+tree. (https://doi.org/10.1145/2312005.2312016)
    • Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta. 2013. The Bw-Tree: A B-tree for new hardware platforms. (https://doi.org/10.1109/ICDE.2013.6544834)
    • Aravind Natarajan and Neeraj Mittal. 2014. Fast concurrent lock-free binary search trees. (https://doi.org/10.1145/2555243.2555256)
    • Arunmoezhi Ramachandran and Neeraj Mittal. 2015. A Fast Lock-Free Internal Binary Search Tree. (https://doi.org/10.1145/2684464.2684472)
    • Aravind Natarajan, Arunmoezhi Ramachandran, and Neeraj Mittal. 2020. FEAST: A Lightweight Lock-free Concurrent Binary Search Tree. (https://doi.org/10.1145/3391438)

Non-blocking data structures require careful reclamation of unused memory in order to avoid accessing already reclaimed memory (use-after-free bugs) and related to that avoiding the ABA problem. Here is a (potentially incomplete) list of safe memory reclamation schemes for non-blocking data structures (as of mid 2021), in no particular order.

1. Free Lists
   • IBM. 1983. IBM System/370 Extended Architecture: Principles of Operation. (https://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/370/princOps/SA22-7085-0_370-XA_Principles_of_Operation_Mar83.pdf)
   • R. Kent Treiber. 1986. Systems programming: coping with parallelism. (https://dominoweb.draco.res.ibm.com/reports/rj5118.pdf)
2. Epoch-based Reclamation (EBR)
   • Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. (https://doi.org/10.1007/3-540-45414-4_21)
   • Keir Fraser. 2004. Practical lock-freedom. (http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.599193)
3. Hazard Pointers (HP) Maged M. Michael. 2002. Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. (https://doi.org/10.1145/571825.571829)
4. Non-blocking Reference Counting
   • David Detlefs, Paul Alan Martin, Mark Moir, Guy L. Steele Jr. 2001. Lock-free reference counting. (https://doi.org/10.1145/383962.384016)
   • Maurice Herlihy, Victor Luchangco, Paul A. Martin, and Mark Moir. 2005. Nonblocking memory management support for dynamic-sized data structures. (https://doi.org/10.1145/1062247.1062249)
5. DEBRA Trevor A. Brown. 2015. Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way. (https://doi.org/10.1145/2767386.2767436)
6. Hyaline Ruslan Nikolaev and Binoy Ravindran. 2019. Hyaline: Fast and Transparent Lock-Free Memory Reclamation (https://doi.org/10.1145/3293611.3331575)
7. Repeat Offender Maurice Herlihy, Victor Luchangco, and Mark Moir. 2002. The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures. DOI
8. Unnamed Zahra Aghazadeh, Wojciech M. Golab, and Philipp Woelfel. 2014. Making objects writable. (https://doi.org/10.1145/2611462.2611483)
9. Unnamed Dave Dice, Maurice Herlihy, and Alex Kogan. 2016. Fast non-intrusive memory reclamation for highly-concurrent data structures. (https://doi.org/10.1145/2926697.2926699)
10. Cadence Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. 2016. Fast and Robust Memory Reclamation for Concurrent Data Structures. (https://doi.org/10.1145/2935764.2935790)
11. Dynamic Collect Aleksandar Dragojevic, Maurice Herlihy, Yossi Lev, and Mark Moir. 2011. On the power of hardware transactional memory to simplify memory management. (https://doi.org/10.1145/1993806.1993821)
12. StackTrack Dan Alistarh, Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit. 2014. StackTrack: an automated transactional approach to concurrent memory reclamation. (https://doi.org/10.1145/2592798.2592808)
13. ThreadScan Dan Alistarh, William M. Leiserson, Alexander Matveev, and Nir Shavit. 2015. ThreadScan: Automatic and Scalable Memory Reclamation. (https://doi.org/10.1145/2755573.2755600)
14. Drop the Anchor Anastasia Braginsky, Alex Kogan, and Erez Petrank. 2013. Drop the anchor: lightweight memory management for non-blocking data structures. (https://doi.org/10.1145/2486159.2486184)
15. Optimistic Access Nachshon Cohen and Erez Petrank. 2015. Efficient Memory Management for Lock-Free Data Structures with Optimistic Access. (https://doi.org/10.1145/2755573.2755579)
16. Automatic Optimistic Access Nachshon Cohen and Erez Petrank. 2015. Automatic memory reclamation for lock-free data structures. (https://doi.org/10.1145/2814270.2814298)
17. QSense Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. 2016. Fast and Robust Memory Reclamation for Concurrent Data Structures. (https://doi.org/10.1145/2935764.2935790)
18. Stamp-it Manuel J. Pöter. 2018. Effective Memory Reclamation for Lock-Free Data Structures in C++. (https://repositum.tuwien.at/handle/20.500.12708/4346)
19. Hazard Eras (HE) Pedro Ramalhete and Andreia Correia. 2017. Hazard Eras—Non-Blocking Memory Reclamation. (https://doi.org/10.1145/3087556.3087588)
20. Interval-based Reclamation (IBR) Haosen Wen, Joseph Izraelevitz, Wentao Cai, H. Alan Beadle, and Michael L. Scott. 2018. Interval-based memory reclamation. (https://doi.org/10.1145/3178487.3178488)
21. Wait-Free Eras Ruslan Nikolaev and Binoy Ravindran. 2020. Universal wait-free memory reclamation. (https://doi.org/10.1145/3332466.3374540)
22. PEBR Jeehoon Kang and Jaehwang Jung. 2020. A marriage of pointer- and epoch-based reclamation. (https://doi.org/10.1145/3385412.3385978)
23. Free Access Nachshon Cohen. 2018. Every data structure deserves lock-free memory reclamation. (https://doi.org/10.1145/3276513)
24. Beware&Cleanup Anders Gidenstam, Marina Papatriantafilou, Håkan Sundell, and Philippas Tsigas. 2005. Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting. (https://doi.org/10.1109/ISPAN.2005.42)
25. Isolde Albert Mingkun Yang and Tobias Wrigstad. 2017. Type-assisted automatic garbage collection for lock-free data structures. (https://doi.org/10.1145/3156685.3092274)
26. NBR Ajay Singh, Trevor Brown, and Ali Mashtizadeh. 2021. NBR: neutralization based reclamation. (https://doi.org/10.1145/3437801.3441625)
27. VBR Gali Sheffi, Maurice Herlihy, and Erez Petrank 2021. VBR: Version Based Reclamation. (https://doi.org/10.1145/3409964.3461817)