  Linearizability has become the key correctness criterion for concurrent data
structures, ensuring that histories of the concurrent object under
consideration are consistent, where consistency is judged with respect to a
sequential history of a corresponding abstract data structure. Linearizability
allows any order of concurrent (i.e., overlapping) calls to operations to be
picked, but requires the real-time order of non-overlapping to be preserved.
Over the years numerous techniques for verifying linearizability have been
developed, using a variety of formal foundations such as refinement, shape
analysis, reduction, etc. However, as the underlying framework, nomenclature
and terminology for each method differs, it has become difficult for
practitioners to judge the differences between each approach, and hence, judge
the methodology most appropriate for the data structure at hand. We compare the
major of methods used to verify linearizability, describe the main contribution
of each method, and compare their advantages and limitations.
