Module 09 · Lesson 7 of 13Free

CAP and PACELC: core distributed tradeoffs

Level

Intermediate

Topic

Distributed systems: replication and consistency

Reading time

18 min

Kartly has 1 speaker left in a festival sale. Replica A confirms its reservation for Asha. Replica B cannot communicate with A, but still shows the speaker as available.

Should B serve that answer to Ravi, or refuse his request?

Kartly now has separate services and replicated data. We’ll follow one product across two regions. The stock count and regional layout are illustrative assumptions for this lesson.

The central question is: when should a replicated service wait, refuse, or answer from local state?

The missing message creates the choice

Start with the simplest regional design. A accepts stock changes. It sends updates to B afterward. Nearby requests read their local copy.

This is the asynchronous copying pattern from Replication models. It works for browsing when temporary differences are acceptable.

Now follow one execution:

1. Both replicas store remaining = 1.
2. Communication between them stops.
3. A reserves the speaker and stores remaining = 0.
4. A confirms the reservation.
5. Ravi’s read reaches B after that confirmation.

B sees the same local state in two possible histories:

No local calculation distinguishes these histories. A clock cannot supply the missing reservation. Repeating the read only reads the same old copy.

If B returns 1, it is wrong in the second history. Guessing 0 is wrong in the first. Waiting for A may never finish if communication never returns.

This is the core CAP impossibility argument: unavailable information prevents a service from guaranteeing both an atomic answer and completion everywhere.^{1Perspectives on the CAP TheoremSeth Gilbert and Nancy A. Lynch, Computer, 2012}

Adding replicas does not change that argument when the answering group cannot learn what the other group completed. We need to decide which promise this operation can give up.

CAP names precise promises

CAP combines consistency, availability and partition tolerance. Its meanings are narrower than their everyday uses.

For CAP, consistency means linearizability: each operation appears to happen at one instant between its request and response.^{1Perspectives on the CAP TheoremSeth Gilbert and Nancy A. Lynch, Computer, 2012} The earlier Consistency models lesson develops that contract.

Asha’s completed reservation must therefore precede Ravi’s later stock read. Operations that overlap can be ordered either way if the operation rules permit it.

A 503 response is useful failure handling, but it does not complete the requested stock read. Returning errors everywhere cannot satisfy CAP availability. A valid “sold out” result is different: it completes a reservation attempt according to the stock rules.

A network partition permits messages to remain undelivered. If that can happen, the service cannot guarantee both C and A for the shared read/write object.^{1Perspectives on the CAP TheoremSeth Gilbert and Nancy A. Lynch, Computer, 2012}

“Choose any two” hides the problem

The common description is “choose any two of three.” That suggests Kartly can select consistency and availability, then choose not to have partitions.

But a configuration setting cannot make a broken link carry messages. During that failure, Kartly still needs a behavior. Brewer explicitly cautions against treating “two of three” as a complete design rule.^{2CAP Twelve Years Later: How the “Rules” Have ChangedEric Brewer, Computer, 2012}

Nor must a consistency-preserving service stop everywhere. One authorized side may continue working. The guarantee of completion at every non-failing node is what it gives up.

CAP tells us which combination is impossible. It does not tell us which failed requests customers should see.

Protect the promise, not every read

Kartly has two distinct product questions.

Must the product page show exact stock? No. An approximate availability label is acceptable if checkout checks again.

May two customers receive the same final reservation? No. One customer would pay and later lose the order.

For this example, a reservation is one atomic operation: check remaining stock and decrement it if positive. A read followed by a separate decrement would introduce a local race before replication even matters.

This choice applies to an operation, not Kartly as a whole. Brewer describes making partition choices at finer boundaries than an entire system.^{2CAP Twelve Years Later: How the “Rules” Have ChangedEric Brewer, Computer, 2012}

For the read/write reservation interface, we favor consistency during partitions: PC in PACELC notation. Approximate catalog reads deliberately offer a weaker contract. They are not evidence that the reservation interface is available everywhere.

The distinction gives the UI a concrete responsibility: never render an approximate browsing value as a confirmed stock hold.

Recovery cannot undo a promise

Suppose Kartly instead allowed both regions to reserve their local final unit.

A confirms Asha’s reservation. B confirms Ravi’s. Each local transaction may be valid against its own copy.

When communication returns, both copies might contain remaining = 0. Comparing only current values would hide the problem. The reservation records reveal two promises backed by one speaker.

Choosing one final database value does not repair the customer experience. Kartly must obtain more stock, cancel an order, or offer compensation.

Our chosen design avoids that particular conflict by refusing independent reservations at B. After reconnection, B catches up from A before it is eligible for any read contract requiring current state.

There is still another failure: A commits a reservation, but its confirmation never reaches the caller. A timeout must not be shown as proof that nothing happened.

Use a idempotency key, a stable identifier for one reservation attempt. A stores the key and reservation result atomically. A retry returns that result instead of taking another unit. Idempotency covers the implementation.

The resulting behavior should be written down before deployment:

This design does not promise survival of permanent loss of A’s storage. Replication durability and safe promotion are separate requirements.

We have chosen failure behavior. We have not yet chosen how much waiting customers experience when everything works.

Healthy networks still cost time

Imagine a seller changes a product description through A. B receives the update asynchronously.

Even with a healthy network, there is an interval when B still has the old description. We must either permit that read or make it wait for authoritative information.

PACELC makes the second question explicit:

• If a partition occurs: availability or consistency?
• Else: latency or consistency?

Abadi introduced this formulation to include tradeoffs outside network failures.^{3Problems with CAP, and Yahoo’s little known NoSQL systemDaniel Abadi, DBMS Musings, 2010}

Latency is not interchangeable with CAP availability. A request that eventually completes after a long wait may satisfy the formal availability condition and still be useless to a customer.

Consider two catalog read paths. The following timings are estimates for this lesson, not measured infrastructure performance.

The extra delay comes from this request path, not from the word “consistency.” Moving the authority closer would change it.

For the catalog read/write interface, local stale reads favor EL. Its partition behavior depends on writes too. If description writes still require A, the interface does not provide CAP availability everywhere.

That is why “local reads” alone cannot justify labeling a whole database PA/EL.

Turn labels into operating rules

Use PACELC as two questions, not a database shopping category. Settings, routing and the operation contract determine the answer.

For each important operation, record:

1. What completed work must this request observe?
2. Which component can authorize its result?
3. What happens when that component cannot be reached?
4. Which communication steps are on the healthy request path?
5. What must happen before normal routing resumes?

These questions expose choices that “strong” or “available” alone leave unspecified.

For Kartly, set a bounded wait on forwarded reservations. When it expires, return a temporary failure or an unknown-outcome response, depending on whether submission may have reached A. Never fall back to locally confirming stock.

A timeout is a policy trigger, not proof that the remote node is dead. Brewer connects this practical timeout decision to the consistency–availability choice.^{2CAP Twelve Years Later: How the “Rules” Have ChangedEric Brewer, Computer, 2012}

Monitor reservation failures separately from catalog latency. Also track replication progress and unresolved reservation attempts. Otherwise a healthy browsing dashboard could hide a checkout outage.

Where this shows up

• Design: a concert ticket booking system: a seat confirmation cannot be independently granted twice.
• Design: an e-commerce checkout: browsing and purchase commitments need different contracts.
• Design: a distributed key-value store: read and write policies must specify partition behavior together.

Our fixed authority makes the tradeoff visible; next, Quorums asks which replica responses can safely authorize progress.

Common mistakes

• Treating a fast error as availability. A temporary error protects the stock contract, but the reservation operation did not complete.
• Equating convergence with correctness. Matching counts after repair do not erase two incompatible customer confirmations.
• Inferring consistency from synchronous copying alone. Read routing and safe authority transfer must also preserve the promised ordering.
• Using one label for every endpoint. An approximate description and a final stock reservation have different acceptable outcomes.
• Treating latency estimates as guarantees. Our arithmetic excludes contention, variable network delay and storage stalls.

Check your understanding

Summary