CAP Theorem
Learned in SE464. Also mentioned in CS451.
The CAP theorem is the most famous result in distributed systems theory.
CAP Theorem
It says that a distributed system cannot achieve all three of the following (you can only pick two):
- Consistency: reads always get the most recent write (or an error).
- Availability: every request received a non-error response.
- Partition tolerance: The system can operate despite network partitions. An arbitrary number of messages between nodes can be dropped (or delayed), since network is unreliable.
The CAP Theorem suggests there are three kinds of distributed systems:
- CP: BigTable and Apache HBase
- AP: DNS
- CA: Impossible in distributed systems
Summary of CAP Tradeoffs
| Property | If Prioritized | Tradeoff |
|---|---|---|
| Availability (A) | Serve responses at all times, even during partitions. | May return stale or inconsistent data. |
| Consistency (C) | Ensure all nodes see the same data at all times. | System becomes unavailable during partitions. |
CAP theorem is misstated…it actually means “when faced with a network partition, do you stay available, or stay consistent?
CAP
CAP proof
Proving CAP If you get availability, you don’t have the consistency :(
If you get your consistency, it’s impossible to get availability, because the partition needs to get updated first…
