The non-blocking work-stealing algorithm of Arora, Blumofe, and Plaxton  (henceforth ABP
work-stealing) is on its way to becoming the multiprocessor load balancing technology of
choice in both industry and academia. This highly efficient scheme is based on a collection of
array-based double-ended queues (deques) with low cost synchronization among local and
stealing processes. Unfortunately, the algorithm.s synchronization protocol is strongly based
on the use of fixed size arrays, which are prone to overflows, especially in the multi programmed
environments for which they are designed. This is a significant drawback since,
apart from memory inefficiency, it means that the size of the deque must be tailored to accommodate
the effects of the hard-to-predict level of multiprogramming, and the implementation
must include an expensive and application-specific overflow mechanism.
This paper presents the first dynamic memory work-stealing algorithm. It is based on a novel
way of building non-blocking dynamic-sized work stealing deques by detecting synchronization
conflicts based on "pointer-crossing" rather than "gaps between indexes" as in the original
ABP algorithm. As we show, the new algorithm dramatically increases robustness and memory
efficiency, while causing applications no observable performance penalty. We therefore
believe it can replace array-based ABP work stealing deques, eliminating the need for application-
specific overflow mechanisms.
*This work was conducted while Yossi Lev was a student at Tel Aviv University, and is
derived from his MS thesis .