Trade-offs in Distributed Systems: CAP Theorem Explained

When you design a distributed system, you face a fundamental choice: what matters most when things break? The CAP theorem frames this choice by saying you cannot have all three desirable properties at once. Consistency means every node sees the same data. Availability means the system always responds. Partition tolerance means the system survives network failures. You get to pick two. This is not a limitation you work around, it is a law of physics applied to networks. Understanding CAP is the cornerstone of system design interviews because it is where all real tradeoff conversations begin.

Quick answer: The CAP theorem says a distributed system can guarantee at most two of: Consistency (all nodes agree), Availability (always responds), or Partition tolerance (survives network splits). Since network partitions happen in the real world, the real choice is consistency-first (CP: Zookeeper, etcd, HBase) or availability-first (AP: Cassandra, DynamoDB). Consistency-first favours correctness; availability-first favours resilience. Know which one your system needs and why.

What is the CAP Theorem?

The CAP theorem, formulated by Eric Brewer in 2000 and later proved by Lynch and Gilbert, states a hard truth: any distributed system can guarantee only two of three guarantees at once.

Consistency (C): Every read returns the latest write. If you write a value to a node and then read from any node, you get that new value. All replicas of the data are identical at any given moment. This is strong consistency or linearizability.

Availability (A): The system always responds to requests, even if some internal nodes have failed. Every request gets a response (success or failure) without indefinite waiting. If a server is down, another one handles it.

Partition tolerance (P): The system continues working even when network partitions occur, that is, when some nodes cannot communicate with others due to network failure. In a true network partition, some subset of the cluster is isolated.

If all three were possible together, distributed systems would be trivial. They are not. Once a network partition occurs, you must choose: honour consistency (reject writes/reads that might return stale data, CP) or honour availability (accept writes and return possibly stale reads, AP). You cannot do both during a partition.

Why Partition Tolerance is Non-Negotiable

Many engineers misunderstand CAP by thinking they can avoid the choice if they design carefully. They cannot. Real networks fail. Packets get lost, switches go down, fibre cables are cut, latency spikes, and BGP routes flap. Partition tolerance is not optional; it is a property you already have if you are running any distributed system at all.

This means the real choice is never "which two of CAP do we want?" The real choice is "do we want CP or AP?" Because partition tolerance will happen whether you plan for it or not. You must handle it. The question is how.

CP Systems: Sacrificing Availability for Correctness

In a CP system, when a network partition occurs, one side of the partition (usually a minority) goes silent rather than serve potentially stale data. This ensures consistency but reduces availability.

How it works: During a partition, a CP system may return errors or timeouts to clients whose requests cannot be routed to nodes holding the authoritative data. The system prioritizes not returning wrong data over always returning a response.

Examples of CP systems:

• Zookeeper: Used for distributed coordination, leader election, and configuration management. Zookeeper uses the Zab (Zookeeper Atomic Broadcast) protocol with a quorum model. A leader is elected by majority vote. If a partition occurs, the side without the majority leader stops serving requests.
• etcd: The key-value store used by Kubernetes. etcd is built on Raft consensus. It requires a quorum (more than half the nodes) to make decisions. During a partition, the minority partition stops serving writes.
• HBase: The Hadoop-based database. HBase uses a master-slave architecture with zookeeper for coordination. Only one region server can serve a shard at a time, enforcing strong consistency through single-writer semantics per region.

Trade-off: You get strong consistency (every read is up-to-date) and correctness guarantees. Your data is never inconsistent across replicas. But during a partition, the minority side returns errors instead of stale data. This feels bad to users (the service is "down") but your data stays correct.

When to choose CP:

• Financial systems where an account balance must never be wrong.
• Distributed locks where two processes must never acquire the same lock simultaneously.
• Coordinating leader election: only one leader can make decisions.
• Small, critical state that must be correct above all else.

AP Systems: Sacrificing Consistency for Resilience

In an AP system, during a partition, both sides keep serving requests and accepting writes, even if they diverge. The system returns a response almost always, accepting that data may temporarily be inconsistent.

How it works: Both sides of the partition continue accepting and returning data. Each node serves its best-known version. After the partition heals, the nodes have conflicting versions of the data. The system uses conflict resolution strategies like last-write-wins, vector clocks, or application-defined merging.

Examples of AP systems:

• Cassandra: A decentralized, leaderless database designed for high availability. Cassandra uses eventual consistency and read-repair. During a partition, each side keeps serving reads and writes. When the partition heals, the system reconciles via anti-entropy repair. Multiple writes to the same key are resolved by timestamp (last-write-wins).
• DynamoDB: AWS DynamoDB's default configuration prioritizes availability. It spreads replicas across availability zones. During an AZ partition, both sides serve requests, returning the latest known version. Writes succeed as soon as they replicate to a local quorum, not a global quorum. This allows very high availability at the cost of eventual consistency.
• Riak: A distributed key-value store that favours availability. Writes are replicated to N nodes asynchronously. During a partition, each partition serves reads and writes independently. The application can specify read and write quorums to tune consistency vs. latency.

Trade-off: You get high availability (almost always a fast response) and low latency (no waiting for quorum acknowledgement). But during a partition, data diverges. Two writes to the same key may both succeed in different partitions, creating a conflict that must be resolved. Applications must handle eventual consistency and potential conflicts.

When to choose AP:

• User-facing caches where stale data is acceptable for minutes or hours.
• Social feeds where the latest posts are best-effort, not a strict contract.
• Recommendation systems where a slightly outdated ranking is fine.
• Global services where latency to a distant quorum is unacceptable.

The CAP Spectrum: A Visual Guide

         /\
        /  \
       / C  \
      /______\
     /        \
    / CP      /\
   /         /PA\
  /__________/____\
        P

CP: Majority side stays consistent.
    Minority side goes silent (unavailable).

AP: Both sides stay available.
    Data diverges during partition,
    reconciles after healing.

Network Partition Scenarios:

Scenario 1: Two partitions, no middle ground

  [Node A] <--//--> [Node B]
  (Partition)

  CP system:  One side fails writes/reads
  AP system:  Both sides serve requests,
              may return different values

Scenario 2: Client and server separated

  [Client] <--//--> [Server with all data]
            Network failure

  CP: Client gets error (no quorum)
  AP: Client has stale cache, serves it

CP Versus AP: A Decision Table

Property           | CP Systems      | AP Systems
-------------------+-----------------+------------------
Consistency        | Strong/strict   | Eventual
Availability       | May return 5xx  | Always responds
Network partition  | Halts minority   | Serves both sides
Conflict scenario  | Cannot happen   | Must handle
Latency            | May be high     | Usually low
Use case           | Finance, auth   | Caches, feeds
Example DB         | etcd, Zookeeper | Cassandra, Dynamo
Writes during split| Minority blocks | Both proceed
Data after healing | No merge needed | Merge conflicts

Common Misconceptions About CAP

Misconception 1: CAP only applies during a partition.

False. CAP describes system behaviour during a partition. At other times, all three properties can coexist. CAP says that when a partition happens, you cannot maintain all three. Since partitions do happen in production, you must design with CAP in mind always.

Misconception 2: You can have CAP if you design well.

No. This is a theorem, not a guideline. It is mathematically proven. No clever architecture avoids it. A system that cannot partition (single-machine database) is not distributed, so CAP does not apply. But any system with replicated data across the network faces CAP.

Misconception 3: CAP is about choosing consistency or availability globally.

Partially true, but incomplete. Modern systems often use hybrid strategies. You might use CP for core metadata (user accounts, transactions) and AP for secondary data (user feeds, analytics). You might also use read-repair and quorum tuning to slide along the spectrum.

Misconception 4: Availability in CAP means the whole system is available.

No. Availability means the system responds to requests, not necessarily in a successful way. A 503 error is technically an available response (the system answered). In practical terms, AP systems favour operational availability (fewer errors) while CP systems favour data availability (quorum-based access).

PACELC: Beyond CAP

CAP focuses on partitions, but what about when there is no partition? That is where PACELC comes in. PACELC says: in the normal case (no partition), you face a trade-off between Latency and Consistency.

• If there is a partition (PAC): choose between Consistency and Availability (CAP as above).
• Else (ELC): choose between Latency and Consistency.

In the no-partition case, a system trying to maintain strong consistency across geographically distant nodes must either wait for all replicas to respond (high latency) or compromise consistency. This explains why so many systems default to eventual consistency at read time: it trades latency for correctness.

Applying CAP in a System Design Interview

When a system design interviewer asks about a distributed cache, database, or coordination service, they are testing whether you understand CAP and can justify your choice.

Interview approach:

1. Identify the partition scenario. Where are the nodes distributed? Across a data center (rare partitions)? Across geographic regions (partitions expected)? Single cluster (CAP irrelevant)?

2. Clarify the requirements. Does the application need strong consistency? How many seconds of stale data are acceptable? What happens if writes fail during a partition?

3. State your choice explicitly. "For the user account store, I would choose CP because correctness is non-negotiable. I would use etcd or Postgres with synchronous replication. For the user feed cache, I would choose AP because availability matters more. I would use Cassandra with tunable consistency."

4. Explain the tradeoff. "During a network partition, the account store might be unavailable to minority partitions, but we guarantee no account data corruption. The feed might show slightly outdated posts for a few seconds, but users always see something."

5. Mention failover and monitoring. "We would monitor partition duration and alert if either store is down for more than X seconds. We would have a runbook to manually failover or merge partitions."

This shows interviewers that you understand the fundamental constraint, not just the definitions.

Frequently Asked Questions

Q: Does CAP apply to single-region databases?

A: Not really. Partitions within a data center are rare (single network). CAP is relevant for distributed databases, caches, and systems that span multiple machines. A single-node database or a tightly coupled cluster in one data center does not face CAP constraints often.

Q: Can I use Postgres for both CP and AP use cases?

A: Postgres with synchronous replication behaves like CP (strong consistency, possible unavailability on minority). Postgres with asynchronous replication behaves like AP (high availability, eventual consistency). The configuration matters more than the database itself.

Q: If my system is AP, do I need conflict resolution?

A: Yes. Once your system serves requests from isolated partitions, you risk conflicting writes. You must either accept last-write-wins semantics, use vector clocks to detect causality, or have applications merge conflicts explicitly.

Q: Is consistency the same as ACID?

A: No. CAP consistency is linearizability (all nodes see the same value). ACID consistency is something else: application-specific invariants (like referential integrity). A system can be ACID-consistent but not linearizable. They are orthogonal.

Q: What does "quorum" have to do with CAP?

A: Quorum is one tool for implementing CP. A write succeeds only when a quorum (more than half) of replicas acknowledge. This ensures consistency but reduces availability if the quorum is unreachable.

Q: When the partition heals, does data magically synchronize?

A: No. In an AP system, you must explicitly reconcile conflicting versions. This is anti-entropy repair (background reconciliation) or read-repair (fixing inconsistency on read). This takes time and coordination.

Practising this with Rehurz

System design interviews often dive into CAP when discussing databases, caches, and replication strategies. Rehurz's system design rounds are spoken technical interviews where you talk through your design and defend tradeoffs under adaptive cross-questioning. You explain why you chose CP for accounts and AP for feeds, and the interviewer challenges your assumptions: "What if the partition lasts 10 minutes? What if users can tolerate inconsistency?" Your answers show whether you truly understand CAP or just memorized definitions.

The scorecard evaluates System Design across multiple dimensions including your ability to justify choices under pressure. Start a free system design interview on Rehurz and get real-time feedback on your reasoning. Your first interview is free, no card required.

Closing Thoughts

CAP theorem is not a limitation to work around. It is a reminder that distributed systems require hard choices. Know your application's needs, pick CP or AP, and explain why during your interview. This clarity distinguishes strong system design candidates from those who memorize without understanding.