Seth Gilbert, Nancy Lynch, “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services,” ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59. [PDF]
In this PODC 2000 keynote speech, Eric Brewer claimed that it is impossible for a distributed system to provide the following three guarantees simultaneously:
- Availability, and
Even though all three are desirable properties, the claim is that one of the three has to be weakened or cannot be satisfied at all.
In this paper, Gilbert and Lynch formalize the problem and subsequently prove it for asynchronous networks. They also show the same for partially synchronous networks by using the concepts of timeouts, and local clocks.
The CAP theorem, by itself, is somewhat intuitive. Consequently, the proofs are very straightforward for the asynchronous case. It becomes slightly more complicated for the (partially) synchronous model though.
While this theorem has been extremely influential in reasoning about the design decisions made by many system developers, I think it can easily be abused to quickly give up on something. For example, getting 2 out of 3 do not mean that some shade of the 3rd cannot be achieved at all. For example, there exist weaker consistency models like causal consistency that can achieve availability and partition-tolerance.