Foundations Distributed Systems

CAP Theorem

You can only guarantee two of Consistency, Availability, and Partition Tolerance — understanding the fundamental constraint of distributed data systems.

⏱ 7 min read

What it is

The CAP Theorem, originally proposed by Eric Brewer in 2000 as the "CAP Conjecture" and formally proven by Gilbert and Lynch in 2002, states that a distributed data system can provide at most two of the following three guarantees simultaneously: Consistency (every read returns the most recent write or an error), Availability (every request receives a non-error response, though it may not be the most recent data), and Partition Tolerance (the system continues to operate even when network messages between nodes are dropped or delayed).

The crucial practical implication is that network partitions are not optional — they are an inevitable reality in any distributed system spanning multiple machines. You cannot eliminate partitions; you can only decide how to respond when they occur. Therefore the real choice in distributed system design is not "C, A, or P?" but rather "when a partition occurs, do we sacrifice Consistency (return potentially stale data — AP system) or Availability (refuse to respond until the partition heals — CP system)?"

Why it exists

Before CAP, engineers often assumed that building distributed data systems was primarily an engineering challenge — make nodes communicate reliably enough and you could have everything. CAP formalized the theoretical limit: no matter how well-engineered the system, there are inescapable trade-offs in the face of network failures. This changed how engineers approach database selection and distributed system design, moving the conversation from "which database is best?" to "what consistency model does this use case require?"

Understanding CAP prevents the common mistake of selecting a distributed database assuming it provides strong consistency while also being highly available — and then being surprised by partition-related failures or stale data in production. It forces the design conversation to explicitly confront the system's behavior during failures, not just during normal operation.

When to use

When selecting a database or data store for a distributed system — CAP classification helps narrow the candidates.
When defining the consistency requirements for a particular use case — financial transactions vs social media feeds have very different needs.
When designing the partition-failure behavior of a system — what should the system do when nodes cannot reach each other?
When communicating with stakeholders about the inherent constraints of distributed data systems and why "just make it always consistent AND always available" is not possible.

When not to use

CAP is a binary model — it does not capture the spectrum of partial consistency guarantees (read-your-writes, monotonic reads, causal consistency) that real systems offer. Use PACELC for a more nuanced analysis.
Do not apply CAP to single-node systems — partition tolerance is irrelevant when there is only one node (though you then have no fault tolerance).
Do not use CAP as a substitute for measuring actual system behavior under your specific failure modes — it is a framework for thinking, not a performance specification.

Typical architecture

The CAP triangle below illustrates the three classifications and real-world systems that exemplify each. Note that CA systems — which sacrifice partition tolerance — are only truly achievable as single-node systems or systems where the network is considered fully reliable (a rare assumption in practice).


            Consistency
                 ▲
                 │
        CP       │       (impossible in practice
    ┌────────────┤        for truly distributed
    │ ZooKeeper  │           systems)
    │ etcd       │
    │ HBase      │  CA
    │ MongoDB*   │◄──── Single-node RDBMS
    │            │      (PostgreSQL standalone,
    └────────────┘       MySQL standalone)
                /\
               /  \
              /    \
             /  AP  \
            / Cassandra\
           / DynamoDB   \
          / CouchDB      \
         / Riak           \
        ────────────────────
   Availability        Partition Tolerance

CP: Choose to reject requests rather than return stale data.
    When a partition occurs, some nodes will refuse reads/writes.
    Example: ZooKeeper refuses reads from isolated nodes.

AP: Choose to return potentially stale data rather than reject requests.
    When a partition occurs, nodes serve their local data.
    Example: Cassandra serves reads from any available node.

Real-world nuance: "consistency" in CAP means linearizability
(the strongest consistency model). Most systems offer weaker
guarantees (causal, eventual) along a spectrum.

Pros and cons

Pros of understanding CAP

Forces explicit discussion of consistency requirements before database selection, not after production incidents.
Prevents unrealistic expectations about distributed system behavior during network failures.
Provides a shared vocabulary for engineers, architects, and stakeholders to discuss fundamental trade-offs.
Guides partition failure behavior design — teams that understand CAP define clear "partition protocols" for their systems.

Limitations of CAP

CAP is binary — it does not capture the rich spectrum of partial consistency guarantees real systems provide.
CAP only applies during network partitions — it says nothing about latency trade-offs in normal operation (see PACELC).
The formal definition of "consistency" in CAP (linearizability) is stricter than most applications require, making many real-world trade-offs invisible.
Often misapplied as "pick any two" as a marketing claim rather than a rigorous framework for failure analysis.

Implementation notes

CP systems: Systems that prioritize consistency over availability during a partition will refuse to serve requests from isolated nodes rather than risk returning stale data. ZooKeeper uses the Zab consensus protocol to ensure all nodes agree before a write is acknowledged; during a partition, the minority partition will not serve writes. etcd uses Raft for the same purpose. These systems are appropriate for leader election, configuration management, and distributed locks — where consistency is critical and brief unavailability is acceptable.

AP systems: Systems that prioritize availability during partitions will serve requests from all nodes, accepting that different nodes may have different views of the data at any moment. Cassandra uses a tunable consistency model (QUORUM, ONE, ALL) and defaults to eventual consistency. Amazon DynamoDB is designed as an AP system by default. These are appropriate for user-facing applications where some stale data is tolerable but timeouts are not — shopping carts, social media feeds, user preferences.

Tunable consistency: Many modern systems (Cassandra, MongoDB, CouchDB) allow tuning the consistency vs availability trade-off per operation. Writing with QUORUM and reading with QUORUM in Cassandra provides strong consistency at the cost of reduced availability and increased latency. Writing with ONE provides high availability but risks reading stale data. This flexibility means CAP classification is not always binary — systems sit at a configurable point along the spectrum.

Common failure modes

Choosing AP but expecting CP behavior: Selecting Cassandra for financial data with the assumption that it will "usually" be consistent — and then discovering split-brain scenarios in production.
Treating partition tolerance as optional: Designing for the CA quadrant with a distributed system, then being unprepared for the network partitions that will inevitably occur.
Ignoring the consistency model: Not specifying the consistency level when querying a tunable-consistency database, accepting the default which may be weaker than the use case requires.
Misapplying to single-node systems: Using CAP to argue for eventually-consistent databases in contexts where a single RDBMS with ACID transactions is simpler and entirely appropriate.

Decision checklist

Have we defined the consistency requirement for this use case: linearizable, sequential, causal, or eventual?
What is the acceptable behavior during a network partition — refuse requests (CP) or serve potentially stale data (AP)?
Does the database we are evaluating match our consistency/availability requirements, not just our performance requirements?
If using a tunable-consistency system, have we specified the consistency level for each operation explicitly?
Is the data being stored financial, transactional, or safety-critical in a way that makes eventual consistency unacceptable?
Have we considered PACELC to understand the latency trade-offs in addition to the partition behavior?
Have we stress-tested the system under simulated network partitions (chaos engineering) to validate its actual behavior against our assumptions?

Example use cases

A payment processor selects a CP database (PostgreSQL with synchronous replication) because consistency is non-negotiable — returning stale balance data could result in overdrafts.
A social media platform's "like count" feature uses an AP store (Cassandra) because showing a count of 1,003 vs 1,004 is less harmful than a timeout.
A distributed configuration service uses ZooKeeper (CP) because all nodes must agree on the current configuration — a split configuration causes split-brain behavior in the application cluster.
A shopping cart service uses DynamoDB (AP) because losing a cart item briefly due to eventual consistency is preferable to the cart timing out entirely during a partition.

PACELC Theorem — the refinement of CAP that accounts for latency trade-offs in normal (non-partition) operation.
Eventual Consistency — the consistency model used by AP systems and how it behaves in practice.
Quality Attributes — consistency and availability are two of the most architecture-significant quality attributes.