Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

✨ Summary

Summary

Gilbert and Lynch formalize Eric Brewer’s conjecture for replicated read/write data objects. They define atomic consistency—equivalent to linearizability for the operations considered—as requiring every operation to appear to occur instantaneously in a single order; availability as eventual termination of every request received by a non-failing node; and partition tolerance as continued operation despite arbitrary message loss between network components. (cs.princeton.edu)

The central impossibility proof uses an indistinguishability argument. A write can complete in one partition component while all messages to a second component are lost. A later read in the second component must still terminate because of availability, but cannot learn about the completed write. Returning the old value violates atomic consistency, while waiting indefinitely violates availability. The paper therefore proves that, in an asynchronous network, atomic consistency and availability cannot both be guaranteed when partitions are possible. It also shows that requiring consistency only when messages are eventually delivered does not avoid the result, because an algorithm cannot distinguish a lost message from an arbitrarily delayed one.

The paper examines the three pairwise combinations of the properties. Atomic consistency with partition tolerance requires weakening liveness during failures; atomic consistency with availability is feasible when partitions are excluded; and availability with partition tolerance requires weaker consistency. In a partially synchronous model with known message and processing-time bounds, timeouts allow systems to distinguish some lost messages from delayed messages. This makes it possible to provide atomic behavior when all messages are delivered while returning stale or otherwise inconsistent data during partitions. The paper introduces Delayed-t consistency, which bounds how long stale behavior may persist after a sufficiently long interval of reliable communication.

The work became the standard formal treatment of Brewer’s CAP conjecture and provided a framework for reasoning about consistency–availability choices in distributed data services. Eric Brewer’s later retrospective notes that researchers and system designers used CAP in discussions of new distributed systems and the NoSQL movement, while also cautioning that the common “two out of three” formulation oversimplifies the theorem’s scope. (researchgate.net) Daniel Abadi’s subsequent PACELC formulation built on CAP by distinguishing the consistency–availability trade-off during partitions from a consistency–latency trade-off during normal operation. (odbms.org) Google’s discussion of Spanner likewise uses CAP to explain why a system can provide strong consistency and high practical availability while still sacrificing availability during actual partitions. (research.google.com)