Understanding CAP Theorem and PACELC

When beginning a dive into System Design, one of the first concepts you come across is the CAP theorem.

Here’s a rundown of how I understand it:

What is CAP?

CAP stands for:

• Consistency
• Availability
• Partition Tolerance

Consistency

Consistency implies that all nodes see the same data at the same time.

In simpler terms:

“All reads see the latest write.”

If a write operation succeeds, every subsequent read should return that updated value.

Availability

Availability means every request receives a response.

That response may not always contain the latest data, but the system remains operational and continues serving requests.

Partition Tolerance

Partition Tolerance means the system continues functioning even when communication between nodes is disrupted.

This can happen due to:

• network failures
• power outages
• hardware failures
• data center outages
• delayed or lost messages between nodes

The system should still continue operating and recover gracefully once communication is restored.

The Core Tradeoff

One very important thing to understand is:

CAP theorem applies specifically to distributed systems, and the tradeoff becomes relevant only during a network partition.

In practical distributed systems, Partition Tolerance is generally considered non-negotiable because network failures are inevitable.

So, when a partition occurs, a system must choose between:

• Consistency OR
• Availability

That gives us two broad categories:

CP Systems

Systems that prioritize:

• Consistency
• Partition Tolerance

These systems may reject or delay requests during a partition in order to avoid serving stale or conflicting data.

AP Systems

Systems that prioritize:

• Availability
• Partition Tolerance

These systems continue serving requests even during partitions, though some responses may contain stale data temporarily.

Let me try to give some simple examples for better understanding.

Different parts of the same application may make different CAP tradeoffs.

For example:

• Banking transaction systems generally prioritize strong consistency.
• Social media feeds often prioritize availability and eventual consistency.

Instagram, for instance, would rather show a slightly stale feed than become unavailable entirely.

On the other hand, banking systems cannot afford inconsistencies like showing incorrect account balances.

Enter PACELC

CAP theorem describes system behavior during a partition.

However, what happens when there is no partition?

That’s where PACELC comes in.

PACELC says:

Even when the system is running normally, there is often a tradeoff between Latency and Consistency.

In short:

• Stronger consistency usually increases latency.
• Lower latency often requires relaxing consistency guarantees.

Why?

Because stronger consistency requires more coordination between replicas before operations can complete.

Understanding Replication and Quorums

To understand this better, let’s define three concepts:

N = Number of replicas

The total number of copies of the data.

W = Write Quorum

For a write operation to be considered successful, acknowledgements must be received from W replicas.

R = Read Quorum

For a read operation to be considered successful, data must be received from R replicas.

A commonly used quorum rule is:

R + W > N

This ensures that read and write operations overlap on at least one replica, helping maintain consistency.

Higher values of R and W generally increase consistency because more replicas must agree before operations complete.

However, this also increases latency because the coordinator must wait for responses from more nodes.

Lower quorum values reduce waiting time and improve latency, but they may allow stale reads.

At this point, there’s a very important thing to remember.

The term “Consistency” in CAP theorem is different from “Consistency” in ACID properties.

CAP Consistency

All nodes agree on the latest write.

ACID Consistency

Database integrity constraints remain valid before and after transactions.

These are related but fundamentally different concepts.

And that, in essence, is the CAP theorem.