Michael-Scott Queue

A Michael-Scott queue is the canonical lock-free queue algorithm, published by Maged Michael and Michael Scott in 1996. It uses a singly-linked list with separate head and tail pointers, both manipulated through compare-and-swap operations, to provide a lock-free queue that permits multiple enqueuers and dequeuers to make progress concurrently. The algorithm's subtlety lies in its handling of the lagging tail pointer, where a dequeuing thread may need to advance the tail itself before completing its operation. The Michael-Scott queue remains the foundation for more advanced structures such as the flat-combining queue.

The Michael-Scott queue is not merely an algorithm. It is a proof that lock-free programming is possible — and that it is harder than anyone wants it to be. Every correct implementation of this paper is a small act of defiance against the chaos of parallel execution.