Eventually Consistent Systems

R. Alexander Miłowski


School of Information, UC Berkeley

The Eventually Consistent Paradigm


...computer scientist Eric Brewer (UC Berkeley), the theorem first appeared in fall 1998. It was published as CAP principle in 1999 and presented as a conjecture by Eric Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC). In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, rendering it a theorem. Wikipedia

It is impossible for a distributed computing system to simultaneously provide:

Facebook, Twitter, et. al. scale by addressing CAP limitations in various ways.

It isn't always by relaxing consistency


A service that is consistent operates fully or not at all. (see Julian Browne)



Your service is always available.


Partition tolerance

No set of failures less than total network failure is allowed to cause the system to respond incorrectly (Gilbert & Lynch)


Interpretations Vary

Recommended read: CAP Twelve Years Later: How the "Rules" Have Changed

The "2 of 3" formulation was always misleading because it tended to oversimplify the tensions among properties. Now such nuances matter. CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare.

The bigger your data, the more you need to worry about the CAP Theorem.

Yet, we've come a long way.

ACID / BASE are more local properties than emergent system properties.