Graduate School and Research Center in Digital Sciences

Consistency in non-transactional distributed storage systems

Viotti, Paolo; Vukolic, Marko

ACM Computing Surveys, Vol.49, N°1, June 2016

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 was 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 further 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. 

Document Doi Arxiv Bibtex

Title:Consistency in non-transactional distributed storage systems
Department:Digital Security
Eurecom ref:4781
Copyright: © ACM, 2016. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Computing Surveys, Vol.49, N°1, June 2016
Bibtex: @article{EURECOM+4781, doi = {}, year = {2016}, month = {06}, title = {{C}onsistency in non-transactional distributed storage systems}, author = {{V}iotti, {P}aolo and {V}ukolic, {M}arko}, journal = {{ACM} {C}omputing {S}urveys, {V}ol.49, {N}°1, {J}une 2016}, url = {} }
See also: