White Papers

Introduction

White papers, ordered alphabetically by subject. The important paper is Drepper's (Miscellaneous section), for absolutely vital background knowledge.

Documents

Counter

• Aspnes, Herlihy, Shavit - Counting Networks (download)

Hash

• Michael - High Performance Dynamic Lock-Free Hash Tables and List-Based Sets (download)

Linked List

• Harris - A Pragmatic Implementation of Non-Blocking Linked-Lists (download)
• Sundell, Tsigas - Lock-Free and Practical Deques and Doubly Linked Lists using Single-Word CAS (download)
• Valois - Lock-Free Linked Lists Using Compare-and-Swap (download])

Miscellaneous

• Drepper - What Every Programmer Should Know About Memory (download)

Queue

• Evequoz - Non-Blocking Concurrent FIFO Queues With Single Word Synchroniation Primitives (download)
• Fober, Orlarey, Letz - Optimised Lock-Free FIFO Queue (download)
• Michael, Scott - Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms (download)
• Shann, Huang, Chen - A practical nonblocking queue algorithm using compare-and-swap (download)

Read-Copy-Update

• McKenney, Slingwine - Read-Copy Update; Using Execution History to Solve Concurrency Problems (download)

Safe Memory Reclamation

• Herlihy, Luchangco, Moir - The Repeat Offender Problem (download)
• Michael - Hazard Pointers; Safe Memory Reclaimation for Lock-Free Objects (download)
• Michael, Scott - Correction of a Memory Management Technique for Lock-Free Data Structures (download)

Skip-list

• Fomitchev, Ruppert - Lock-Free Linked Lists and Skip Lists (download)
• Herlihy, Lev, Luchangco, Shavit - A Provably Correct Scalable Concurrent Skip List (download)

Stack

• Hendler, Shavit, Yerushalmi - A Scalable Lock-Free Stack Algorithm (download)

Trees

• Bronson, Casper, Chafi, Olukotun - A Practical Concurrent Binary Search Tree (AVL) (download)
• Braginsky, Petrank - A Lock-Free B+tree (download)
• Kim, Cameron, Graham - Lock Free Red Black Trees Using CAS (download)