The Michael-Scott lock-free FIFO queue keeps a permanent dummy node plus separate head and tail pointers, and a thread enqueuing may find the tail pointer lagging one node behind the real last node. Why is the design shaped that way, and what does a thread do when it observes a stale tail?

## Why a queue is harder than a stack A stack mutates one pointer, so a single compare-and-set is enough. A FIFO queue is modified at two places: items enter at the tail and leave at the head. Two separate pointers let enqueuers and dequeuers work independently — the whole point, since a shared single point would serialise both — but they introduce two new problems: the pointers can be inconsistent with each other, and near-empty queues make the two ends interact. ## The dummy node The queue always contains at least one node, a **sentinel** or dummy whose value is never returned. An empty queue is `head == tail == dummy`, `dummy.next == null`. This buys two things. First, **the ends never alias in a way that forces cooperation**: enqueue always appends after the last node and dequeue always consumes the node *after* head, so in the common case one writes `tail`-side state and the other writes `head`, with no overlap. Without a sentinel, inserting into an empty queue would have to update both pointers atomically, which single-word compare-and-set cannot do. Second, it removes null special cases from the middle of each operation, which is where concurrent algorithms usually go wrong. ## Enqueue is two steps, deliberately ``` enqueue(v): node = new Node(v, next=null) loop: t = read(tail) next = read(t.next) if t != read(tail): continue // snapshot went stale if next != null: // tail is lagging compare_and_set(tail, t, next) // help: advance it continue if compare_and_set(t.next, null, node): // step 1: link compare_and_set(tail, t, node) // step 2: swing tail (may fail) return ``` Step 1 is the **linearization point**: the moment `t.next` changes from null to the new node, the item is in the queue and every subsequent operation will see it. Step 2 is bookkeeping. Because the two are separate, a thread can be preempted, page-faulted or killed between them, leaving the tail one node behind. That state is *legal*, not corrupt — the invariant the algorithm maintains is only "tail points to the last node or the one before it". ## Helping Every operation begins by checking whether the tail is lagging (`tail.next != null`) and, if so, performing the missing compare-and-set on behalf of whoever left it that way before retrying its own work. Dequeue does the same check when it finds `head == tail` with a non-null next, since otherwise it could wrongly report the queue empty while an item is present. Helping is what makes the structure **lock-free**. Without it, a thread stalled between its two steps would leave the tail permanently stale and could block others — a blocking algorithm with no lock in sight. With it, no thread's stall prevents anyone from completing: any interrupted operation can be finished by any other thread. Note also that the helping compare-and-set is allowed to fail and is simply ignored — failure means someone else already advanced the tail, which is exactly the outcome wanted. ## Dequeue ``` dequeue(): loop: h = read(head); t = read(tail); next = read(h.next) if h != read(head): continue if next == null: return EMPTY // truly empty if h == t: compare_and_set(tail, t, next); continue // help, then retry value = next.value // read before unlinking if compare_and_set(head, h, next): return value ``` The successful compare-and-set on head is the linearization point of a dequeue. The old dummy is discarded and the node just consumed becomes the new dummy — which is why the value must be read out *before* the swing, since afterwards that node is the sentinel and may be recycled. ## Costs and caveats - **Two hot lines.** Head and tail are each written frequently, so both become coherence hot spots. Placing them on separate cache lines is essential; otherwise enqueuers and dequeuers false-share and the separation of ends buys nothing. - **Allocation per item.** Every enqueue allocates a node, which puts memory management on the hot path; bounded array-based ring buffers avoid this and usually outperform the linked design when a fixed capacity is acceptable. - **Reclamation.** Threads dereference nodes that others may be removing concurrently, so freeing them safely needs a deliberate scheme; that is a separate body of technique and a prerequisite for any real implementation. - **Progress.** Lock-free, not wait-free: a thread can lose its compare-and-set races indefinitely. ## The transferable idea The general lesson is broader than the queue: when an update needs more than one atomic step, publish the *essential* step first, make every intermediate state legal and detectable, and require every participant to complete any half-finished operation it encounters. That pattern — legal intermediate states plus helping — is how multi-step lock-free algorithms are built in general.