CAP, PACELC, and the Tradeoffs Every Distributed System Has to Make

CAP Theorem

Say a research team claims they've built a sorting algorithm that runs in O(log n). Is that possible?

No. To sort anything, you have to at least look at every element once, so time complexity can never be better than O(n) — that's the true lower bound. Comparison-based sorting algorithms (the ones we typically use) can't beat O(n log n). But when the elements are bounded — say, all values between 1 and 10 — non-comparison algorithms like counting sort can hit that O(n) lower bound directly.

The point: it's mathematically proven what is and isn't achievable here. No amount of clever engineering gets you below O(n), just like it can't get comparison-based sorting below O(n log n).

Distributed systems have their own version of this. CAP theorem tells us what is and isn't possible in distributed systems — a lower bound on what a distributed system can guarantee, no matter how well it's engineered. It's built on three properties: Consistency, Availability, and Partition Tolerance.

Consistency

We always talk about consistency in the context of data. When a write happens to the database, consistency asks: are the reads in line with that write?

Reads happen at two places: caches, and replicas.

Consistency is irrelevant to stateless servers, and irrelevant when data is immutable — in both cases there's nothing that can go "stale."

There are three types of consistency:

Eventual Consistency

A system is eventually consistent when reads eventually line up with writes, at some point in time. The system will have stale reads until then.

Example: replicas sync with the write database every 5 minutes. A counter updates every 1 minute. The replicas catch up at t=5, t=10, and so on — eventually consistent.

Immediate Consistency

A system is immediately consistent when reads and writes happen atomically — typically via a two-phase commit. At any point in time, reads are guaranteed to be in line with the write database.

It's always good to have immediate consistency, but it's hard to achieve, and it costs you latency to get it.

No Consistency

A system has no consistency when there's data loss — some writes never make it anywhere durable. This is only acceptable when intermediate values genuinely don't matter and some data loss is fine (e.g. certain analytics pipelines).

Availability

We talk about availability in terms of how a server deals with requests.

• If a healthy server denies a healthy request → low / no availability (any 5xx — the server can't reach a critical resource it needs).
• If a healthy server satisfies a healthy request → high availability.
• If a server crashes mid-request and the client has to retry after a timeout → this is not counted as low availability. The client retries, the load balancer routes elsewhere, and the system moves on.
• If a bad request comes in and the server denies it (e.g. an auth error, 4xx) → the system is still considered highly available. The server responded correctly; the client was at fault.

Partition Tolerance

Picture a set of servers connected by cables, all talking to each other. If a network failure isolates some of them, and as a result some services go down — but the system as a whole keeps running — we call the system partition tolerant.

Example: Amazon's payment service goes down due to a network failure, but users can still browse the catalog, wishlist items, add things to their cart.

If a system has to shut down entirely because of a network failure, it is not partition tolerant.

Example: stock exchanges (BSE/NSE/NYSE/SSE) — a partition takes the whole exchange down.

Availability vs Partition Tolerance

Situation: Someone wants to withdraw money from an ATM. The ATM backend checks the account balance, then updates it — both in the primary DB and in the replicas.

Under normal conditions, this just works — the write reaches the DB and the read replica stays in sync.

Now introduce a network partition between the backend DB servers.

Low on consistency, high on availability

The user withdraws money. Because of the partition, the server can't sync up with the replica. A later balance check gets routed to the stale replica and returns the old balance — as if the withdrawal never happened.

Low on availability, high on consistency

Alternatively: the withdrawal request is denied outright, because the backend detects it can't sync with the replica and refuses to risk serving incorrect data.

CAP Theorem: Pick 2

CAP Theorem states that you can only pick 2 out of Consistency (always meaning immediate consistency here), Availability, and Partition Tolerance. With this, we get only 3 possible types of systems:

A+P System

Designed to choose high availability and partition tolerance. These systems have eventual consistency, and yes — they do have stale reads.

Example: social media platforms.

C+P System

Designed to choose high consistency and partition tolerance. These systems have immediate consistency, and no — they do not have stale reads.

A commonly cited example here is ATMs, but as we saw earlier, that is not quite right in practice — most real banking systems are actually AP, favoring uptime and reconciling inconsistencies afterward (that is the whole overdraft-fee mechanism). A more accurate example of a true C+P system would be something like a stock broker placing an order against a live balance check, where the request is flatly denied rather than risking an incorrect trade.

C+A System

Designed to choose high consistency and high availability. These systems are not partition tolerant — if there is any network partition, the entire system goes down. They have immediate consistency, and no stale reads.

Example: stock exchanges. Stock exchange companies cannot afford to be low-available or inconsistent, so to avoid network partition failures in the first place, they do a lot of engineering — their servers are connected by many duplicate fiber optic cables.

Another definition of CAP theorem

At the scale of Google, can a system choose to have network failures bring the entire system down? No. Google has millions of servers, and somewhere, network partitions are happening every single day.

The majority of systems we see are designed to be partition tolerant. They have to choose either availability or consistency. We mostly see AP systems in the real world.

So the definition of CAP theorem becomes:

1. Partition tolerance is non-negotiable.
2. We pick either availability or consistency.

PACELC Theorem

PACELC theorem is an extension of CAP theorem.

To understand it, consider two situations:

• When there is a network partition → choose Consistency or Availability
• When there is no network partition → choose Latency or Consistency

No matter whether there is a partition or not, you only ever have two options to choose between. Even in the best-case scenario — a perfectly healthy network — you still cannot get both low latency and immediate consistency at the same time.

Master Slave Replication

Basic Setup

• We'll have one Master. Writes will always go to the master.
• We'll have more than one Slave. Reads will always go to the slaves.

Replication Factor (X): number of total copies of the same data.
X = 1 Master + y slaves

• If X = 3, then 1 Master + 2 Slaves
• If X = 4, then 1 Master + 3 slaves
• If X = 5, then 1 Master + 4 slaves

Where do the writes and reads happen?

• Writes always happen at the master
• Reads always happen at the replicas

What happens if the Master goes down?
Re-election happens, and one of the slaves becomes master.

What if the old master comes back online?
It joins as a slave.

What if a slave goes down?
A new slave is spun up. We should always maintain the replication factor (X).

Why do we need an odd number of servers?
For tie-breaking (quorum).

Master Slave Replication With No Consistency

	Where	Availability	Latency
Reads	At one of the slaves	High	Low
Writes	Only at Master	High	Low

• Writes always go to the master. Reads always go to one of the slaves.
• We have more than one replica, so read availability is always high.
• We write to only one place — even if the master crashes, re-election happens — so write availability is high. And because you're writing to only one place, write latency is low, not high.
• Can there be data loss? Yes — if the master's HDD fails before it syncs up, all unsynced data is lost.
• Can stale reads happen? Yes — if data is requested before a sync completes.

Master Slave Replication with Eventual Consistency

	Where	Availability	Latency
Reads	At one of the slaves	High	Low
Writes	At 2 places (1 Master + 1 slave)	Decent	Decent

• Writes always happen at two places (master and a slave). Reads always go to one of the slaves.
• We have more than one replica, so read availability is always high.
• Write availability is decent because we're doing atomic writes at 2 places, and we need at least 2 servers online for a successful write.
• Can there be data loss? No — we're writing to more than one place.
• Can there be stale reads? Yes — possible if we request data before a sync happens.
• How do we write to more than one place atomically? We use a two-phase commit for atomic writes, which gradually increases write latency.

Master Slave Replication with Immediate Consistency - Writing everywhere

	Where	Availability	Latency
Reads	One of the Replicas	High	Low
Writes	At every server	Very Low	Very High

• Writes happen at every server, and if a write fails at even one server, we roll back at every other server.
• Writing to every server will definitely drop the latency, because you're bottlenecked by the slowest server — so write latency is very high, not very low.
• Reads have high availability because we have more than one replica.
• Reads have low latency because we just have to read from one server.
• Can we have stale reads? No — we're writing to all the servers, so every server always has the latest data.
• We use a two-phase commit to write to all the servers.

Master Slave Replication with Immediate Consistency - Writing to more than half servers (Quorum)

	Where	Availability	Latency
Reads	More than half of the servers	Decent	Decent
Writes	More than half of the servers	Decent	Decent

• We write and read to more than half of the servers.
• The availability here is a middle ground — not the "very low" of write-everywhere, but not the "very high" of writing to a single master either — since we now need a majority of servers to be reachable, not all of them.
• Latency is also a middle ground, since we're waiting on a majority rather than every single server.
• Can we have stale reads? No — because more than half the servers have the latest data.
• How do we make sure we're reading the latest data? We add timestamps to each request and store it in the DB. While fetching, we return the value with the latest timestamp across all the reads.
• If any server crashes while reading, we'll always have at least one server with the latest data.

Master Slave Replication - Tunable Consistency

We don't need to write or read to more than half of the servers, as long as there's an overlap — that's enough to achieve immediate consistency.

Now we can tune our system:

• If your system is read-heavy, choose to write to more servers.
• If your system is write-heavy, choose to read from more servers.

Can we have stale data? Depends on how we tune it.

Parameters:

• R = Number of reads
• W = Number of writes
• X = Replication Factor

The rules:

• R = 1, W = 1 → No Consistency
• R = 1, W > 1 → Eventual Consistency
• R + W ≤ X, W > 1 → Eventual Consistency
• R + W > X → Immediate Consistency

Wrapping Up

The mental model worth keeping:

• Partition tolerance isn't a choice — at any real scale, it's the water you swim in.
• So the actual decision is Consistency vs. Availability during a partition, and Latency vs. Consistency the rest of the time.
• And master-slave replication, once you add the R/W/X model, isn't stuck at one point on that spectrum — it's a dial you can turn based on whether your system reads more than it writes, or the other way around.