Skip to content

What consistency does your key-value store actually provide?

03/05/2012

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.

from 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
Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: