Papers
Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
Seth Gilbert, Nancy Lynch · ACM SIGACT News, 2002
The problem: an informal conjecture becoming a formal proof
In 2000, Eric Brewer presented in a talk the idea that a distributed service could not simultaneously deliver three desirable properties: consistency, availability and network partition tolerance. The observation was influential among practitioners, but it remained a conjecture, with neither a precise definition of the three terms nor a mathematical proof. Gilbert and Lynch write this paper precisely to close that gap: to give formal definitions, in the vocabulary of asynchronous distributed systems, for consistency, availability and partition tolerance, and then to prove that all three cannot coexist. The practical motivator is the boom of replicated web services in the late 1990s: as data came to be spread across multiple geographically distant nodes to scale and survive failures, messages between those nodes can be lost or delayed indefinitely, and the question stops being theoretical: architects of real systems needed to know which guarantee to give up when the network failed. The paper positions itself as a reasoning tool, not as a rule that forbids combinations: it makes clear that the impossibility holds when a partition actually occurs, and that systems can behave differently before, during and after it.
The three properties defined precisely
The core of the paper is to give exact meaning to each letter of CAP. Consistency is defined as behavior equivalent to having a single up-to-date copy of the data: any read, after a completed write, must return that value (or a more recent one), as if the operations were executed in a single global order, even with replicas. Availability means that every request sent to a non-failing node of the system must eventually receive a response — the system cannot simply stay silent for a legitimate client. Partition tolerance means that the system keeps working even when messages between groups of nodes are lost or arbitrarily delayed by the network, so that the nodes cannot communicate with each other for a period. The paper assumes the asynchronous model: there is no known bound on how long a message may take to arrive, which is the most pessimistic (and most general) formalization of a real network. It is this definition of partition — arbitrary loss or delay of messages between subsets of nodes, without the rest of the system knowing whether the message was lost or just delayed — that underpins the whole proof that follows.
The proof: why you can't have all three at once
The proof uses an argument by contradiction with a minimal scenario of two nodes that replicate the same data and are separated by a network partition. Suppose the system is consistent, available and partition-tolerant. During the partition, a client writes a new value to the first node; since the system is available, that node must respond to the client even though it cannot tell the second node about the update, as the partition blocks the message between them. Then another client reads the data from the second node; since the system is also available, that second node is required to respond — but it never received the update, so it can only return the old value. This violates consistency, because the read should reflect the most recent write. The central point of the proof is that, during the partition, each isolated node has no way to know whether the other is merely slow or truly unreachable; it must decide locally between responding with possibly stale data (keeping availability, losing consistency) or refusing to respond until it is sure (keeping consistency, losing availability). Since this choice is unavoidable once the partition happens, the three properties cannot be guaranteed simultaneously in this model.
Beyond the proof: the partially synchronous model and the trade-off in practice
After proving the impossibility in the pure asynchronous model, the paper discusses a scenario closer to real networks: the partially synchronous model, in which nodes have local clocks and can use timeouts to estimate whether a message is merely delayed or a partition has actually occurred. In this setting, the authors show that it is still not possible to escape the theorem, but systems gain a practical tool to manage the trade-off in a more informed way, instead of blindly choosing between consistency and availability. This means designers can, for example, tolerate temporary inconsistency during the estimated duration of a partition and restore consistency as soon as communication is reestablished, instead of simply refusing all responses. The paper emphasizes that the result is about what happens during and because of the partition, not a claim that consistency and availability are always incompatible. Decades later, this distinction becomes even more explicit in a popular extension called PACELC, proposed by Daniel Abadi (2010/2012), which adds to CAP the idea that even without any partition (E, 'else'), replicated systems still have to choose between latency and consistency (L versus C) — recognizing CAP as a proof about the rare case of the partition, and not about the whole day-to-day operation of a distributed system.
See the ideas at work
Practice the designs that use this paper in the System Design school.