# What consistency does your key-value store actually provide?

An operation on the register is either a read (i.e., get) or a write (i.e., put). Using a global clock, we assign each operation a start time and a finish time. We say opera- tion A time-precedes operation B, written as A < B, if A finishes before B starts. If neither A < B nor B < A, then A and B are said to be concurrent with each other, written as A||B. It is easy to see that this time precedence relation imposes a partial order on the operations. A valid total order is one that conforms to this partial order. Given a total order, each read has a unique most recent write, if any. A register has the following semantics if there exists a valid total order that satisfy the corresponding conditions.

A register is said to be safe if a read not concurrent with any writes returns the value of the most recent write, and a read concurrent with some writes returns any value.

A register is said to be regular if a read not concurrent with any writes returns the value of the most recent write, and a read concurrent with some writes returns either the value of the most recent write, or the value of one of the concurrent writes.

A register is said to be atomic if every read (regardless of whether they are concurrent with any writes or not) returns the value of the most recent write. It is easy to see that safety is weaker than regularity, which is in turn weaker than atomicity.

*What consistency does your key-value store actually provide?*by Eric Anderson, Xiaozhou Li, Mehul A. Shah, Joseph Tucek, Jay J. Wylie — Hewlett-Packard Laboratories