PBS: Probabilistically Bounded Staleness

Peter Bailis, UC Berkeley

Wednesday 2/21/12  11:30am, 465 Soda Hall

Eventually consistent semantics provide almost no guarantees regarding the recency of data returned (unbounded staleness of versions). Despite these weak guarantees, many data store users opt for eventual consistency in practice–why? It’s often faster to contact fewer replicas, and it also results in higher availability. However, instead of relying on anecdotal evidence, we can quantitatively demonstrate why eventual consistency is “good enough” for many users. We can predict the expected consistency of an eventually consistent data store using models we’ve developed, called Probabilistically Bounded Staleness. Moreover, we can describe the reasons why data is or isn’t consistent. It turns out that, in practice, and in the average case, eventually consistent data stores often deliver consistent data. Using PBS predictions, we can optimize the trade-off between latency and consistency and better understand why so many data store users choose eventual consistency in practice.