  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.
Nevertheless, for applications that do not require all guarantees offered by
linearizability, recent research has focused on improving performance and
scalability of concurrent data structures by relaxing their semantics.
  In this paper, we present local linearizability, a relaxed consistency
condition that is applicable to container-type concurrent data structures like
pools, queues, and stacks. 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. We
investigate theoretical and practical properties of local linearizability and
its relationship to many existing consistency conditions. We present a generic
implementation method for locally linearizable data structures that uses
existing linearizable data structures as building blocks. Our implementations
show performance and scalability improvements over the original building blocks
and outperform the fastest existing container-type implementations.
