Local Linearizability

The semantics of concurrent data structures is usually given by a sequential specification and a consistency condition. Linearizability is the most popular consistency condition due to its simplicity and general applicability. Then again, linearizability is known to require extensive synchronization which may jeopardize performance and scalability. For applications that do not require all guarantees offered by linearizability, recent research has therefore focused on improving performance and scalability by relaxing the semantics of concurrent data structures. In this paper, we present local linearizability, a relaxed consistency condition that is applicable to pools, queues, stacks, and many other container-type concurrent data structures. While linearizability requires that the effect of each operation is observed by all threads at the same time, local linearizability only requires that for each thread T, the effects of its local insertion operations and the effects of those removal operations that remove values inserted by T are observed by all threads at the same time. Local linearizability is strictly weaker than linearizability on most containers including pools, queues, and stacks. We present a generic and easy method for implementing locally linearizable data structures using existing linearizable data structures as building blocks. In our experiments, our implementations show improvements in performance and scalability compared to the original linearizable building blocks. Moreover, our locally linearizable implementations outperform the fastest existing container-type implementations.