Contention at the top
A Treiber stack funnels every push and pop through one atomic top pointer. Under heavy load that pointer becomes a hot spot where compare and swaps fail and retry endlessly. The elimination backoff stack adds a clever escape hatch.
Cancel opposing pairs
The insight is that a push and a pop happening at the same time can cancel each other directly. A push handing its value to a waiting pop is equivalent to the value entering and leaving the stack, so the central structure need not be touched at all.
- When a compare and swap on top fails, the thread backs off to an elimination array
- A push posts its value to a random slot and waits briefly for a partner
- A pop visiting a slot with a waiting push takes the value, and both leave satisfied
Scaling under load
Exactly when contention is worst, opposing operations are plentiful, so many pairs eliminate in parallel across different slots without ever reaching top. The stack thus scales up as load increases rather than collapsing, while still falling back to the central structure when no partner appears.
Key idea
The elimination backoff stack lets a stalled push and pop swap a value in a side array, scaling under contention because opposing operations cancel without touching the top.