The Michael-Scott queue is often seen as the first and most foundational lock-free fifo queue. It implements a linked list of one node per item, and uses compare-and-swap loops to correctly update pointers. It is a nice design, which is often used as a base-line, and whose idea is often part of many new data structure designs.
The code was introduced in the paper Simple, fast, and practical non-blocking and blocking concurrent queue algorithms.
Elias Johansson Kåre von Geijer [email protected]