System Design CAP Theorem

The CAP Theorem, proposed by computer scientist Eric Brewer in 2000, states that a distributed data system can guarantee at most two out of three properties: Consistency, Availability, and Partition Tolerance. Understanding CAP helps designers make informed trade-offs when building distributed databases and services.

No system can achieve all three simultaneously — network partitions are a fact of life in distributed systems. So the real question is: when a partition occurs, does the system sacrifice consistency or availability?

The Three Properties Explained

Consistency (C)

Every read returns the most recent write or an error. All nodes in the distributed system always see the same data at the same time. There are no stale reads.

Consistent System:
Write "balance = $100" on Node 1
Read from Node 2 → Returns $100  ✓ (same as Node 1)
Read from Node 3 → Returns $100  ✓ (same as Node 1)

ALL nodes agree on the same value. Zero stale data.

Availability (A)

Every request receives a response (success or failure), but not necessarily the most up-to-date data. The system never refuses to answer — it keeps serving requests even if some nodes are down.

Available System:
Node 2 is behind on replication
Read from Node 2 → Returns $90 (stale, but still responds!)

System always answers. Responses may be slightly outdated.

Partition Tolerance (P)

The system continues operating even when network communication between some nodes is disrupted (a network partition). Nodes cannot reach each other, but the system keeps running.

Network Partition:
+----------+  X X X  +----------+
|  Node 1  |---------|  Node 2  |
| (USA)    |  (link  | (Europe) |
+----------+  broken)+----------+

A partition-tolerant system keeps both nodes running independently
and handles the split gracefully.

Why Only Two Out of Three?

In a real distributed system, network partitions always happen eventually — cables cut, routers crash, data centers lose connectivity. Because partition tolerance is non-negotiable in any distributed system, the practical choice is between Consistency and Availability during a partition event.

Network Partition occurs between Node 1 and Node 2:

Option 1: Choose Consistency
→ System refuses to answer until partition heals
→ Availability sacrificed → Some users cannot read or write
→ But all data is accurate when system responds

Option 2: Choose Availability
→ Both nodes keep responding with whatever data they have
→ Consistency sacrificed → Users may see outdated data
→ But the system never goes down

CAP in a Diagram

                 Consistency (C)
                      /\
                     /  \
                    /    \
                   / CP   \
                  /        \
                 /    ??    \
                /____________\
Availability(A)     AP        Partition
                           Tolerance (P)

Real distributed systems choose:
CP  → Consistent + Partition Tolerant (sacrifice availability)
AP  → Available + Partition Tolerant (sacrifice consistency)

CA  → Consistent + Available (only works without network partitions)
    → Only possible in single-node or non-distributed systems

CP Systems: Consistency + Partition Tolerance

CP systems prioritize correctness over uptime. When a partition occurs, the system refuses to respond rather than return potentially stale data. This is critical for financial and transactional systems where incorrect data causes real harm.

Example: Bank Transfer System (CP)

Normal state:
Account A: $1,000

Network partition between Node 1 and Node 2:

User tries to transfer $500:
CP System says: "Cannot complete transaction — network issue"
(Returns error or timeout)

Why: Better to reject the request than to show $500 debited
     on one node but not the other.

Result: System is unavailable during partition.
Data is always consistent when it responds.

Real CP databases: HBase, Zookeeper, MongoDB (default config), Redis (in certain modes)

AP Systems: Availability + Partition Tolerance

AP systems prioritize uptime over perfect data accuracy. When a partition occurs, the system keeps responding even if some responses contain slightly outdated data. After the partition heals, nodes reconcile their differences to reach eventual consistency.

Example: Social Media Feed (AP)

Normal state:
Post count: 1,250 likes

Network partition between Node 1 and Node 2:

User A on Node 1 likes the post: Node 1 shows 1,251 likes
User B on Node 2 likes the post: Node 2 shows 1,251 likes

After partition heals:
Both nodes reconcile → Actual count is 1,252 likes
Both nodes update to 1,252

Result: System always responds. Temporarily shows different counts.
Data converges to correct value eventually.

Real AP databases: Cassandra, DynamoDB, CouchDB, Riak

CA Systems: Consistency + Availability

True CA systems only work when there are no network partitions — meaning they are not truly distributed. Traditional single-server relational databases (MySQL, PostgreSQL without replication) fall here because there is only one node, so partitions cannot occur.

Single-node MySQL:
→ No network partition possible (only one machine)
→ Consistent (all reads see latest write)
→ Available (always responds)
→ But: zero fault tolerance. Server crashes = system down.

In practice, any system that claims to be CA is either not truly distributed or is ignoring the reality of network partitions.

Real-World CAP Trade-off Examples

PACELC: The Extended Model

The PACELC model extends CAP by adding a second trade-off for normal operation (when no partition exists). PACELC stands for: Partition → choose A or C; Else → choose L (Latency) or C (Consistency).

CAP only covers behavior during a network partition.
PACELC also covers the normal case:

During normal operation (no partition):
→ Option 1: Low Latency (respond fast, maybe with slightly stale data)
→ Option 2: Strong Consistency (check all replicas before responding, slower)

Examples:
Cassandra:  PA/EL → Available in partitions, Low latency normally
DynamoDB:   PA/EL → Available in partitions, Low latency normally
Zookeeper:  PC/EC → Consistent in partitions, Consistent normally (slower)

Eventual Consistency and Conflict Resolution

AP systems often use eventual consistency — after a partition heals, all nodes eventually agree on the same data. But during the partition, conflicting writes can occur on different nodes. Conflict resolution determines what happens when two nodes disagree.

Last-Write-Wins (LWW)

Node 1: User updates name to "Alice" at T=100
Node 2: User updates name to "Alicia" at T=101

After partition heals:
T=101 is more recent → "Alicia" wins → T=100 update discarded

Simple but can silently lose data.

Vector Clocks

Each operation carries a version vector:
Node 1 write: [Node1:1, Node2:0] → name="Alice"
Node 2 write: [Node1:0, Node2:1] → name="Alicia"

After partition:
Vectors are concurrent (neither is a successor of the other)
→ Conflict detected! Requires human or application resolution.

Amazon's Dynamo uses this to detect conflicts and presents both versions to the application.

Merge Functions (CRDT)

Conflict-free Replicated Data Types (CRDTs) are data structures designed so all concurrent updates can be automatically merged without conflicts. A simple example is a counter that only increments — you can always add all increments from all nodes to get the correct total.

Common Misconceptions About CAP

• Misconception: CAP means picking two and ignoring one permanently. Reality: The trade-off only applies during a network partition. Normal operations can be both consistent and available.
• Misconception: All CP or AP databases are identical. Reality: Databases offer a spectrum of consistency levels, not just binary CP or AP.
• Misconception: Strong consistency is always better. Reality: Strong consistency increases latency and reduces availability. AP with careful design often delivers better user experience.

Summary

The CAP Theorem defines the fundamental trade-off in distributed systems: during a network partition, a system must choose between staying consistent (CP) or staying available (AP). Partition tolerance is not optional in real distributed systems — network failures always happen. The right choice depends entirely on the business requirements. Financial systems choose CP because stale data causes real harm. Social platforms choose AP because brief inconsistency is far less damaging than downtime. Designing for the correct CAP properties is one of the most important decisions in system architecture.