Article development led by queue.acm.org

How can applications be built on eventually
consistent infrastructure given no guarantee
of safety?

BY PeteR BaiLiS aND aLi GhoDSi eventual Consistency today: Limitations, extensions, and Beyond

in a July 2000 conference keynote, Eric Brewer, now VP of engineering at Google and a professor at the University of California, Berkeley, publicly postulated the CAP (consistency, availability, and partition tolerance) theorem, which would change the landscape of how distributed storage systems were architected. 8

Brewer’s conjecture—based on his experiences building infrastructure for some of the first Internet search engines at Inktomi—states that distributed systems requiring always-on, highly available operation cannot guarantee the illusion of coherent, consistent single-system operation in the presence of network partitions, which cut communication between active servers. Brewer’s conjecture proved prescient: in the following decade, with the continued rise of large-scale Internet services, distributed-system architects frequently dropped “strong” guarantees in favor of weaker models—the most notable being eventual consistency.

Eventual consistency provides few
guarantees. Informally, it guarantees
that, if no additional updates are made
to a given data item, all reads to that
item will eventually return the same
value. This is a particularly weak mod-
el. At no given time can the user rule
out the possibility of inconsistent be-
havior: the system can return any data
and still be eventually consistent—as it
might “converge” at some later point.
The only guarantee is that, at some
point in the future, something good
will happen. Yet, given this apparent
lack of useful guarantees, scores of us-
able applications and profitable busi-
nesses are built on top of eventually
consistent infrastructure. How?