Describe how a concurrent LIFO stack can be built using nothing but an atomic compare-and-set on a single head pointer — the design usually called the Treiber stack. Walk through push and pop, state the progress guarantee it provides, and say where it performs badly.

## The structure The stack is a singly linked list of immutable nodes plus one mutable shared word: `head`. Each node holds a value and a `next` pointer that is written once, before the node becomes reachable. Because the only shared mutable location is `head`, the whole algorithm reduces to installing a new head value atomically — an operation single-word compare-and-set provides directly. ``` push(v): node = new Node(v) loop: observed = read(head) node.next = observed if compare_and_set(head, observed, node): return pop(): loop: observed = read(head) if observed == null: return EMPTY next = observed.next if compare_and_set(head, observed, next): return observed.value ``` ## Why it is correct The compare-and-set is the pivot. It installs the new head only if the head still equals the value the thread based its work on; otherwise the thread's view is stale and it starts over. So every successful operation is applied to a state it actually observed, and the linked list is never seen half-updated: a pushed node's `next` is set before the node is published, and a popped node is unlinked in one indivisible step. Each operation has a single **linearization point** — the successful compare-and-set — which is why the stack is linearizable: every operation appears to take effect instantaneously at that moment, and the observed order matches some legal sequential LIFO history. ## Progress The design is **lock-free but not wait-free**. Lock-free because a compare-and-set only fails when another thread's succeeded, so at every point of contention someone completed an operation; the system cannot deadlock or livelock, and no thread's stall can block another (nobody holds anything). Not wait-free because a specific thread may lose every race: under sustained contention its snapshot can be invalidated on every attempt, with no bound on retries. Since threads never hold ownership of the structure, a thread preempted between the read and the compare-and-set costs nothing to anyone else — that is the property a mutex-based stack cannot offer. ## Where it performs badly Every operation, push or pop, writes the same word. That word's cache line must be owned exclusively by whichever core is writing, so it migrates from core to core on every single operation. The result is a hardware serialisation point: throughput approaches one operation per cache-line ownership transfer, and per-thread throughput *falls* as threads are added. Retry loops make it worse, because failed attempts also acquire the line and burn bandwidth while accomplishing nothing. A second cost is that each push allocates a node, so a high-rate stack pushes memory-management pressure into the hot path. ## Known improvements - **Backoff.** On repeated compare-and-set failures, wait a randomised, growing interval before retrying. This reduces wasted traffic and often raises throughput substantially, at the cost of latency for the backing-off thread. - **Elimination.** Observe that a concurrent push and pop cancel out: if they meet, the pusher can hand its value directly to the popper and both return without touching `head` at all. Implementations use a small side array of exchange slots; threads that fail the head compare-and-set try to pair up there before retrying. This turns the head from a bottleneck into a fast path used only when the operation mix is unbalanced, and it makes the stack scale with core count where the plain version does not. - **Batching.** Push or pop several items per head update where the API permits it, amortising the ownership transfer. ## Boundaries to acknowledge Two real problems sit adjacent to this algorithm and belong to their own body of technique rather than to the algorithm's shape. First, `pop` dereferences `observed.next` on a node another thread may be popping at the same instant, so freeing or reusing nodes safely requires a deliberate memory-reclamation scheme. Second, a head pointer that changes and returns to the same value between a thread's read and its compare-and-set can let a stale operation succeed. A strong answer names both as prerequisites for a production implementation, without pretending the bare pseudocode above is deployable as written. ## What to emphasise The interesting content is that a full concurrent container falls out of one atomic word plus a retry loop; that its progress guarantee is lock-free rather than wait-free and why; that its linearization point is the successful compare-and-set; and that its bottleneck is physical (one contended line) rather than logical, which is what motivates elimination and backoff.