  Over the years, different meanings have been associated to the word
consistency in the distributed systems community. While in the '80s
"consistency" typically meant strong consistency, later defined also as
linearizability, in recent years, with the advent of highly available and
scalable systems, the notion of "consistency" has been at the same time both
weakened and blurred.
  In this paper we aim to fill the void in literature, by providing a
structured and comprehensive overview of different consistency notions that
appeared in distributed systems, and in particular storage systems research, in
the last four decades. We overview more than 50 different consistency notions,
ranging from linearizability to eventual and weak consistency, defining
precisely many of these, in particular where the previous definitions were
ambiguous. We further provide a partial order among different consistency
predicates, ordering them by their semantic "strength", which we believe will
reveal useful in future research. Finally, we map the consistency semantics to
different practical systems and research prototypes.
  The scope of this paper is restricted to non-transactional semantics, i.e.,
those that apply to single storage object operations. As such, our paper
complements the existing surveys done in the context of transactional, database
consistency semantics.
