  Linearizability, the de facto correctness condition for concurrent data
structure implementations, despite its intuitive appeal is known to lead to
poor scalability. This disadvantage has led researchers to design scalable data
structures satisfying consistency conditions weaker than linearizability.
Despite this recent trend, sequential consistency as a strictly weaker
consistency condition than linearizability has received no interest.
  In this paper, we investigate the applicability of sequential consistency as
an alternative correctness criterion for concurrent data structure
implementations. Our first finding formally justifies the reluctance in moving
towards sequentially consistent data structures: Implementations in which each
thread modifies only its thread-local variables are sequentially consistent for
various standard data structures such as pools, queues and stacks. We also show
that for almost all data structures, and the data structures we consider in
this paper, it is possible to have sequentially consistent behaviors in which a
designated thread does not synchronize at all. As a potential remedy, we define
a hierarchy of quantitatively strengthened variants of sequential consistency
such that the stronger the variant the more synchronization it enforces which
at the limit is equal to that enforced by linearizability.
