The CAP theorem is a formal impossibility result for replicated, distributed systems: under a specified asynchronous model, consistency and availability cannot both be guaranteed when a network partition occurs. Partition tolerance is therefore treated as necessary rather than optional. section 9.4 section 9.4.1
Consistency is a safety property: a successful read reflects the most recent write, or the read reports failure. Availability is a liveness property: every read eventually receives a successful response, even if it is stale. A partition divides the network so messages between segments are lost. section 9.4.2
The formal result assumes:
- Nodes communicate through an asynchronous network and have no access to clocks. section 9.4.3
- A permanent partition prevents information from flowing between separated nodes. section 9.4.3
- During that partition, a system must sacrifice consistency or availability, commonly yielding CP or AP behavior. section 9.4.1
A two-replica partition
Nodes N1 and N2 begin with value v0, but cannot communicate after a permanent partition. A client writes v1 to N1, then reads from N2. If N2 responds, it can return only stale v0; if it refuses until learning v1, availability is lost. The contradiction shows why both guarantees cannot hold together. section 9.4.3
Table 9.5 Conjecture vs. theorem
| Conjecture |
Theorem |
|
| Consistency |
Single-copy serializability |
Linearizability of r/w register |
| Availability |
Some node responds timely. |
Any node responds eventually. |
| Partitioning |
Temporary |
Permanent |
Compare Brewer’s intuitive conjecture with Gilbert and Lynch’s formal theorem, including their different meanings of consistency, availability, and partitioning. section 9.4.2
The familiar “pick two out of three” slogan is misleading because realistic systems must tolerate partitions. The practical choice is whether to preserve stronger consistency or continued availability when communication fails. section 9.4.1 section 9.5
