Probabilistically Bounded Staleness for Practical Partial Quorums : Summery

I recently gave a presentation on paper by PeterBailis and his friends at University of California Berkley
http://vldb.org/pvldb/vol5/p776_peterbailis_vldb2012.pdf

Unlike other papers does not propose a consistency model rather the paper talks about a probabilistic model to predict the staleness of data . They introduce term called Probabilistic bounded staleness to provide bounds on staleness of data wrt both version and clock time. I found the paper pretty interesting and I feel that because of the move more and more towards eventual consistency the question "How Eventual and How Consistent " makes more sense as it will help the users to choose the best available read and write quorum configuration for there system. Or in words it provides a lens for analyzing, improving, and predicting the behavior of existing, widely deployed systems.

Quorum System :  A quorum system is a collection of sets where all pairs of sets intersect.

A (strict) quorum System Q* over a universe U is a set system over U such that for every
    Q1, Q2 Є Q, Q1 П Q0 ≠ Ф Each Q Є Q is called a quorum.
N – No of nodes that store Replica
W – No of Replicas acknowledge the receipt of the update before the update completes
R – the number of replicas that are contacted when a data object is accessed through a read operation
For Strong  Consistency : R+W  > N (Read ,Write set Overlap)
For Eventual Consistency :  R+W =< N

* Probabilistic Quorum Systems : Dahlia Malkhi

Probabilistic Quorum Systems
Relax  Quorum Intersection Property
Hold with High Probability 1 – ε (ε small Number)
Scaling no of replicas increase probability

A quorum system obeys PBS k-staleness consistency with probability 1 –psk where psk is the probability of non-intersection with one of the last k independent quorums.

 N = 3, R = W = 1
Probability of returning a version
Within 2 versions is 0.5
Within 3 versions is 0.703
Within 5 versions > 0.868
Within 10 versions > 0.98

t-visibility is the probability that a read operation, starting t seconds after a write commits will observe the latest value of data.
t- inconsistency window.


Assumption :  reads occur instantaneously
and writes commit immediately after W replicas there is no delay acknowledging the write to the coordinating node.

A quorum system obeys PBS <k-t> -staleness consistency if, with probability 1- pskt, at least one value in any read quorum will be within k versions of the latest committed version when the read begins, provided the read begins t units of time after the previous k versions commit.



 


* http://vldb.org/pvldb/vol5/p776_peterbailis_vldb2012.pdf