2015/10/01 by Seep Goel, Pooja Aggarwal, Goel, Seep +3 · 3 voices
Computer Science · #Distributed systems and fault tolerance #Parallel Computing and Optimization Techniques #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.1510.00116
In this paper, we describe a novel algorithm to create a con- current 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.