CAP Theorem (CS)
The CAP theorem states that a distributed data store can provide at most two of the following three guarantees simultaneously during a network partition: Consistency (every read receives the most recent write), Availability (every request…
Definition
The CAP theorem states that a distributed data store can provide at most two of the following three guarantees simultaneously during a network partition: Consistency (every read receives the most recent write), Availability (every request receives a response), and Partition tolerance (the system continues operating despite network failures between nodes).
Overview
The CAP theorem, formulated by Eric Brewer and later formally proven by Seth Gilbert and Nancy Lynch, is one of the most influential ideas in Distributed Systems design. Because network partitions — situations where nodes cannot communicate with each other — are an unavoidable reality in any system spanning multiple machines, partition tolerance is generally treated as a given rather than an optional trade-off. This means the practical choice most distributed systems actually face is between consistency and availability specifically when a partition occurs. Systems that prioritize consistency (often called CP systems) will refuse to serve a request, or block until it can be resolved correctly, rather than risk returning stale or conflicting data during a partition — traditional relational databases configured for strict consistency and many Consensus Algorithm-based systems lean this way. Systems that prioritize availability (AP systems) will keep responding to requests even during a partition, potentially returning slightly outdated data, and reconcile any conflicts once the partition heals — a strategy often paired with eventual consistency models common in many NoSQL databases. It's important to note the CAP theorem strictly applies to behavior during a network partition; outside of a partition, well-designed systems can and do offer both strong consistency and high availability. In practice, many modern systems don't sit purely at one extreme but offer tunable consistency levels per operation, letting application developers choose the right trade-off for each specific use case rather than for the whole system uniformly. Understanding the CAP theorem is essential when choosing or designing a database for a distributed application, since it frames a core, unavoidable engineering trade-off rather than a solvable problem. It is often mentioned alongside Load Balancing Algorithm in this space.
Key Concepts
- Describes an unavoidable trade-off in distributed data systems
- Consistency, Availability, and Partition tolerance are the three properties
- Only two of the three can be fully guaranteed during a network partition
- Partition tolerance is generally treated as mandatory, not optional
- CP systems favor correctness over uptime during a partition
- AP systems favor uptime over strict correctness during a partition
- Many real systems offer tunable, per-operation consistency levels