# Michael-Scott queue
The **Michael-Scott queue** (Maged Michael and Michael Scott, 1996) is the standard lock-free multi-producer multi-consumer queue algorithm, and the concrete design behind the general term [[lock-free-queue]]. Its full implementation, enqueue, dequeue, the dummy-node trick, and the tail-helping mechanism, is covered there; this article focuses on what made the paper's contribution significant rather than repeating the code.

## What the paper actually solved

Before 1996, lock-free queue designs either restricted themselves to single-producer or single-consumer scenarios, or paid for full multi-producer multi-consumer generality with heavier synchronization than a queue should need. Michael and Scott's contribution was a fully general MPMC lock-free queue using only CAS, no locks anywhere, with `head` and `tail` as two separate atomic pointers and a dummy node that removes the need for special-case handling of the empty-queue transition.

## The key idea: helping

The algorithm's distinctive move is that a thread which notices `tail` has fallen behind (another thread linked a new node but hasn't yet swung `tail` forward) helps finish that update itself before proceeding, rather than waiting for the original thread to get around to it.

```
if tail->next != NULL:
    # someone linked a node but hasn't advanced tail yet
    CAS(tail, stale_tail, tail->next)   # help them, then retry own operation
```

This **cooperative helping** pattern is what guarantees the algorithm is lock-free in the formal sense: system-wide progress is guaranteed (some thread always completes its operation in bounded steps) even though any individual thread's progress isn't guaranteed on its own, since a slow or descheduled thread's incomplete work gets finished by whichever other thread runs into it next.

## Legacy

The Michael-Scott queue's design pattern, separate head/tail pointers, a dummy node, and helping for a lagging pointer, became the template that most subsequent lock-free queue designs are compared against or built on top of. Production concurrent queue implementations (Java's `ConcurrentLinkedQueue`, for instance) are directly based on it. Like any CAS-based structure that frees nodes, it needs a memory reclamation scheme ([[hazard-pointer|hazard pointers]] or [[rcu|epoch-based reclamation]]) layered on top to be safe in practice; the paper itself predates hazard pointers, which came later specifically to address this class of algorithm.