A Wait-Free Stack
đź“ś Abstract
In this paper, we describe a novel algorithm to create a concurrent wait-free stack. To the best of our knowledge, this is the first wait-free algorithm for a general purpose stack. In the past, researchers have proposed restricted wait-free implementations of stacks, lock-free implementations, and efficient universal constructions that can support wait-free stacks. The crux of our wait-free implementation is a fast pop operation that does not modify the stack top; instead, it walks down the stack till it finds a node that is unmarked. It marks it but does not delete it. Subsequently, it is lazily deleted by a cleanup operation. This operation keeps the size of the stack in check by not allowing the size of the stack to increase beyond a factor of W as compared to the actual size. All our operations are wait-free and linearizable.
✨ Summary
The paper presents a linked-list-based concurrent stack intended to provide both wait-freedom and linearizability. Its principal design choice is to separate logical removal from physical deletion. A pop operation reads the top once, traverses predecessor links, and atomically marks the first unmarked node. Marking is the logical linearization event for a successful pop; an empty result is returned when traversal reaches the sentinel. Because pop operations do not modify the top pointer, multiple pops can proceed concurrently and do not directly contend with pushes.
Pushes use an announce array, monotonically increasing phase numbers, and helping. Threads help the oldest pending push so that a delayed thread cannot starve. A successful push first attaches its node through an atomic next-pointer update and then advances the top pointer. The top-pointer update is the push linearization point. The protocol ensures that a push request is inserted at most once, even when multiple threads help it.
Marked nodes are physically removed lazily. The cleanup mechanism groups nodes into ranges of size W; when sufficient activity has occurred for a range, one cleanup request is selected and helped by participating threads. Cleanup bypasses a contiguous sequence of marked nodes by changing a predecessor link. This bounds the list’s physical size by a factor related to W and the number of logically live stack elements, preventing pop traversals from growing without limit.
The claimed worst-case complexities are O(N) for ordinary pushes, O(NWS) for cleanup-sensitive operations, and O(NWS) worst-case for pop, where N is the number of threads, S is the logical stack size, and W is the cleanup parameter. The paper reports an amortized pop cost of O(NS) across groups of W operations. Thus, the design trades inexpensive common-case operations for infrequent, potentially expensive cleanup; choosing W is workload-dependent. The implementation relies on atomic compare-and-set, atomic marking, fetch-and-add-style counters, and automatic or otherwise safe memory reclamation.
The work was initially released as arXiv:1510.00116 on October 1, 2015, and subsequently appeared as an ICDCIT 2016 Springer chapter, pages 43–55. (arxiv.org) A later wait-free array-based stack, FA-Stack, represents the same broader research direction—practical wait-free stacks with bounded operation steps—but the available source does not establish that it directly derives from this paper. (researchgate.net) More recent work on wait-free deques treats a stack as a restricted deque and reports a wait-free stack with polylogarithmic amortized step complexity, demonstrating continued progress on the complexity and scalability challenges addressed by this paper. (drops.dagstuhl.de) The search found no clear evidence of substantial industry adoption or an explicit direct technical lineage from this specific implementation; its documented impact is primarily as an early general-purpose wait-free stack design within concurrent-algorithm research.