Nonblocking Concurrent Data Structures with Condition Synchronization



We extend the classic notion of linearizability to cover requests -- operations that must wait for some other thread to establish a precondition. Our approach identifies two linearization points for such operations. The first marks when a request becomes visible to other operations; the second when it is fulfilled and takes effect. By placing both linearization points within the purview of object semantics, we allow those semantics to specify not only the effects of operations, but also the order in which pending requests may be fulfilled. We use the term dual data structure to describe concurrent object implementations that may hold requests and/or data. By reasoning separately about the intervals before, after, and between an operation's linearization points, we obtain meaningful definitions of non-blocking dual data structures. As concrete examples, we present lock-free dualstacks and dualqueues and experimentally compare their performance with lock-based and nonblocking alternatives.