  Designing an efficient concurrent data structure is an important challenge
that is not easy to meet. Intuitively, efficiency of an implementation is
defined, in the first place, by its ability to process applied operations in
parallel, without using unnecessary synchronization. As we show in this paper,
even for a data structure as simple as a linked list used to implement the set
type, the most efficient algorithms known so far are not concurrency-optimal:
they may reject correct concurrent schedules.
  We propose a new algorithm for the list-based set based on a value-aware
try-lock that we show to achieve optimal concurrency: it only rejects
concurrent schedules that violate correctness of the implemented set type. We
show empirically that reaching optimality does not induce a significant
overhead. In fact, our implementation of the concurrency-optimal algorithm
outperforms both the Lazy Linked List and the Harris-Michael state-of-the-art
algorithms.
