Module 7: Reliability and the Consistency Tradeoff

5. PACELC: beyond CAP

Description

By the end of this lesson you will understand PACELC, the extension of CAP that Daniel Abadi proposed to plug the theorem's biggest gap: CAP only talks about the rare case —the partition—, and is silent about the common case —when the network is healthy—. PACELC reads like a sentence with two branches: if Partition, choose between Availability and Consistency; Else (no partition), choose between Latency and Consistency. You will understand why that second tradeoff (latency versus consistency) that CAP ignores exists: strong consistency always costs latency, partition or not, because keeping the copies linearizable requires coordination —synchronous replication, quorum, waiting for confirmations— and that coordination takes time. You will meet the four resulting classes (PA/EL, PC/EC, PA/EC, PC/EL) with examples of real systems, and you will classify Enlace as PA/EL: available under partition (you decided that in lesson 4) and low-latency the rest of the time —exactly the profile a redirect served 4,000 times per second needs—.

This matters because CAP, on its own, leaves a false impression: that outside partitions "you have C and A for free" and there is nothing else to decide. But systems spend 99.99% of the time without a partition, and in all that time there is a tradeoff that does operate and that defines the system's everyday behavior: do I pay the coordination cost so that every read sees the last write (strong consistency, more latency), or do I let the replicas respond without coordinating (eventual consistency, less latency)? PACELC names that decision and makes it part of the design. Understanding it gives you a classification tool that real distributed databases use to describe themselves, and it lets you make Enlace's decision completely —not just "what do I do under partition" (CAP) but "what do I do the rest of the time" (the Else of PACELC)—, which is where its latency is really at stake.

Connection to the module: this lesson completes the framework lesson 4 left half-done. CAP gave you the "if Partition" branch (Enlace is AP); PACELC adds the "Else" branch (Enlace is EL), and together they give the complete classification PA/EL. It is also the direct bridge to lesson 6: the "EL" of PACELC —preferring low latency to strong consistency when the network is healthy— is exactly what, brought down to practice, is called eventual consistency, which lesson 6 formalizes and measures with Enlace's numbers. The border holds: here we classify the tradeoff; how the coordination that gives strong consistency is implemented (quorum protocols, consensus, two-phase commit) is the resilience guide and the distributed systems one. We decide which side of the tradeoff Enlace lives on, we do not build the protocol.

Confirming each sale by phone costs time, even if the phone works

Think of it this way, going back to the two branches from lesson 4. There the phone line went down (the partition) and the branches had to choose between serving or coordinating. But now I want you to look at the case in which the line works perfectly, because there too there is a decision, and CAP ignores it completely.

Imagine the store adopts a rule of maximum coordination: "before selling the last unit of any product, the branch must call the other to confirm it is still available". With the line healthy, this rule works —the two branches are always perfectly coordinated, they never oversell—. But look at the cost: every sale now includes a phone call. The customer waits while the employee dials, says hello, asks "any left?", listens to the answer and hangs up. Coordination is not free; it is paid in time, on every operation, even when everything works.

Now imagine the opposite rule: "sell with the information you have at your own counter; do not call anyone". Sales are instant —the customer does not wait for any call—, but every so often the two branches end up slightly uncoordinated (they sell the same last unit almost at the same time) and they reconcile later. Here you sacrificed coordination (consistency) in exchange for speed (latency), without there being any partition —the line is perfect, you simply chose not to use it on every sale—.

That is the decision PACELC puts on the table and that CAP does not see: even when the network works (Else), there is a tradeoff between consistency and latency, because strong consistency requires the coordination call, and the call costs time. CAP only looks at the case in which the line goes down; PACELC looks at both cases —the line down (P) and the line healthy (E)— and in each one there is a different tradeoff.

The PACELC statement

PACELC (pronounced "pass-elk") reads like a conditional sentence with two branches. Daniel Abadi formulated it in 2012 like this:

If there is a Partition, how does the system trade off Availability and Consistency? Else (when running normally, no partition), how does the system trade off Latency and Consistency?

In other words: if there is a partition (P), how does the system negotiate between availability (A) and consistency (C)? Else, operating normally, how does it negotiate between latency (L) and consistency (C)?

The two branches and their options:

                    is there a partition?
                          │
          ┌───────────────┴───────────────┐
      P (partition)                    E (else: healthy network)
          │                                │
   choose A or C                     choose L or C
          │                                │
    ┌─────┴─────┐                    ┌─────┴─────┐
   PA          PC                   EL          EC
 available   consistent         low latency    consistent
 under       under              (does not      (coordinates on
 partition   partition          coordinate     each op, slower)
                                on each op)

Notice that the C appears in both branches, and it is no coincidence: strong consistency is what costs in both cases. Under partition, it costs availability (to be consistent, you refuse to respond → CP). Without a partition, it costs latency (to be consistent, you coordinate on every operation → EC). Strong consistency is always paid for; PACELC just clarifies with what it is paid for in each situation. The "if P" branch of PACELC is exactly the CAP theorem; Abadi's contribution is the "Else" branch, which CAP never had.

Why strong consistency costs latency (even without a partition)

This is the central idea of the lesson, and it is worth understanding well because it is not obvious. Why does strong consistency cost latency even with a healthy network?

Remember from lesson 4 that strong consistency = linearizability = every read sees the most recent write, as if there were a single copy. Now think about how that is achieved with several copies (replicas). When you write a value, for any replica read next to return the new value (never the old one), the write has to have propagated and been confirmed on the replicas before being considered successful. That is synchronous replication: the write waits for enough replicas to confirm "I have it now" before responding "done" to the client. And waiting for those confirmations —which travel over the network, even if the network is healthy— takes time: it is extra latency on every write, and sometimes on every read (if you read from a quorum to guarantee the newest datum).

The alternative is asynchronous replication: the write is confirmed as soon as one copy accepts it (the primary), and it propagates to the replicas afterward, in the background. The write is fast (it does not wait for anyone), but for a little while the replicas are behind —the replication lag of module 5—, so a read from a replica may return the old value. That is eventual consistency, and its prize is low latency: nobody waits for coordination.

  STRONG CONSISTENCY (EC)             EVENTUAL CONSISTENCY (EL)
  write ──► primary                   write ──► primary ──► "done" (fast)
                │  waits                             │
                ▼  confirmations                     ▼  propagates later
           replica 1  ✓                         replica 1  (arrives later)
           replica 2  ✓                         replica 2  (arrives later)
                │
           "done" (slow: I waited for all)     reads may see old datum
                                               for a little while (replication lag)

Here is the knot: the coordination that gives strong consistency is intrinsically slower, and that slowness exists whenever there are replicas, with or without a partition. That is why PACELC needs the "Else" branch: the latency-vs-consistency tradeoff does not appear only when the network fails; it appears every time a replicated system decides whether to wait for coordination (consistent, slow) or not wait for it (eventual, fast). CAP, looking only at partitions, could not even name this tradeoff.

The four classes, with real examples

Combining the two branches gives four classes. Every distributed system falls into one, and describing yourself with PACELC is today a common way for databases to declare their character.

Class	Under partition	Without partition (Else)	Examples and profile
PA/EL	available (AP)	low latency (EL)	Cassandra, Dynamo (Amazon's original design), Riak. "Prioritize responding always and fast; accept eventual consistency." The high-availability, low-latency profile. (Note: the managed product DynamoDB is usually classified PA/EC, not like the original Dynamo.)
PC/EC	consistent (CP)	consistent (EC)	Classic RDBMS with synchronous replication, VoltDB, HBase. "Prioritize exactness always, even if it costs availability under partition and latency the rest of the time."
PA/EC	available (AP)	consistent (EC)	MongoDB (in its default configuration: under partition it stays available, but with a healthy network it guarantees consistent reads/writes) and some tunable databases. Less common than the two pure ones.
PC/EL	consistent (CP)	low latency (EL)	Under partition they stop to be exact, but with a healthy network they prioritize latency. Yahoo's PNUTS is the canonical example.

The two "pure" classes —PA/EL and PC/EC— are the most common and the easiest to reason about, because they take the same attitude in both branches: PA/EL always prefers to respond (available under partition, fast the rest of the time), and PC/EC always prefers to be exact (consistent under partition, coordinated the rest of the time). The two mixed ones (PA/EC, PC/EL) exist and are valid, but they are cases of systems that change priority depending on whether or not there is a partition. Many modern databases are tunable: they let you choose the class per operation or per configuration, instead of fixing it for the whole system.

Worked example: Enlace is PA/EL

Let us classify Enlace with the two branches, leaning on what we already decided and on its numbers.

"if Partition" branch → PA (we already decided this in lesson 4). Under a partition, resolve must keep responding with whatever copy it has, even if it may be a few seconds stale, because refusing to redirect is worse than a slightly stale URL. Enlace chooses A over C under partition: it is PA.

"Else" branch → EL (this lesson's new decision). With a healthy network —99.99% of the time— Enlace serves ~4,000 reads per second, and each one is a user waiting to be redirected. The Else question is: do I pay coordination on every resolve to guarantee that I return the most recent URL (EC, slower), or do I let the closest replica respond without coordinating (EL, faster)? The answer falls under its own weight when you look at the numbers:

# The cost of coordinating (EC) versus not coordinating (EL) on Enlace's read path
qps_read = 4000                 # ~4,000 reads/s (anchor numbers)

lat_local_ms  = 1               # read from the closest replica, without coordinating (EL)
lat_quorum_ms = 15              # read from a quorum to guarantee the newest datum (EC)

extra_ms = lat_quorum_ms - lat_local_ms
print(f"latency per read:  EL = {lat_local_ms} ms   EC = {lat_quorum_ms} ms")
print(f"coordinating (EC) adds {extra_ms} ms to EACH of {qps_read:,} reads/s")
print(f"in exchange for guaranteeing something a redirect almost never cares about")

What to expect. When you run it:

latency per read:  EL = 1 ms   EC = 15 ms
coordinating (EC) adds 14 ms to EACH of 4,000 reads/s
in exchange for guaranteeing something a redirect almost never cares about

Enlace chooses EL: it does not pay coordination on every resolve, it lets the closest replica respond in ~1 ms, and it accepts that very occasionally the datum is a few seconds behind. Paying 15 ms per read —multiplying by 15 the latency of the system's most frequent operation— to guarantee an exactness that a redirect almost never needs would be a terrible deal. It is EL over EC.

Putting the two branches together: Enlace is PA/EL. Available under partition, fast the rest of the time, eventual consistency in both situations. It is the same class as Cassandra and DynamoDB, and not by chance: Enlace has the archetypal profile those systems were designed for —read-heavy, data tolerant to lag, priority on responding always and fast—. That classification is not an academic label: it is a design decision that says "do not build synchronous coordination on the resolve path; serve from the closest replica". Lesson 6 formalizes it as eventual consistency and measures its lag window.

Common mistakes

Believing that without a partition "you have C and A for free" and there is nothing to decide (of scope). What happens: someone who only knows CAP designs as if the only consistency tradeoff occurred during partitions, and ignores the coordination latency they pay the rest of the time. Why it happens: CAP, literally, does not mention the no-partition case. How to spot it: if your replicated system has strong consistency and you did not ask yourself what extra latency it costs with a healthy network, you skipped the "Else". How to fix it: use PACELC —always ask both branches—; the Else (latency versus consistency) usually matters more in practice than the if-P, because it happens all the time.

Confusing the Else tradeoff with the partition one (conceptual). What happens: someone says "we chose availability over consistency" to justify a fast read without coordination, when what they actually chose was latency over consistency (the Else), not availability. Why it happens: the two branches share the C and get mixed up. How to spot it: if there is no partition and you are talking about "availability", you probably mean "latency". How to fix it: remember that under partition the tradeoff is A-vs-C, and without a partition it is L-vs-C; name them differently so as not to confuse yourself when classifying.

Treating the class as an immovable global label (of precision). What happens: someone says "my database is PA/EL" and assumes that every operation behaves that way, when many modern systems are tunable per operation (a write with strong quorum, an eventual read, in the same system). Why it happens: the four classes sound like fixed categories. How to spot it: if your database lets you choose the consistency level per query (for example, LOCAL_QUORUM versus ONE in Cassandra) and you classify it with a single label, you are oversimplifying. How to fix it: classify per operation or per path when the system allows it —Enlace can be EL on resolve (read) and use a stronger guarantee on the generation of the short_code (write), as we will see in lesson 6—.

Exercises

Exercise 1 — Read the PACELC sentence. For each system, complete the two branches ("if P → ?, Else → ?") and give the resulting class. (a) A system that under partition stops accepting writes so as not to diverge, and with a healthy network waits for a quorum's confirmation on every write. (b) A system that under partition keeps responding with local data, and with a healthy network reads from the closest replica without coordinating. (c) Enlace's resolve.

See solution

(a) if P → stops to be exact = PC; Else → coordinates on every write = EC. Class: PC/EC (the classic synchronous RDBMS: exactness always, at the cost of availability under partition and latency the rest of the time).
(b) if P → responds with the local copy = PA; Else → reads without coordinating = EL. Class: PA/EL (Cassandra/DynamoDB: respond always and fast, eventual consistency).
(c) Enlace's resolve: PA/EL, same as (b). Available under partition (lesson 4), low latency the rest of the time (this worked example).

Exercise 2 — The cost of EC. Enlace receives ~4,000 reads/s. If it chose strong consistency on the read path (EC), every resolve would read from a quorum at 15 ms instead of the local replica at 1 ms. (a) How much extra latency per read? (b) If a typical user makes 5 clicks on short links in a session, how much extra wait time do they accumulate by choosing EC instead of EL? (c) Explain in one sentence why, for a redirect, that cost buys almost nothing.

See solution

(a) 15 - 1 = 14 ms extra per read. Multiplies by 15 the latency of Enlace's most frequent operation.
(b) 5 clicks × 14 ms = 70 ms extra of accumulated wait per session, just to coordinate every redirect.
(c) Because a short_code almost always points to the same URL its whole life, so "the last version" and "the version from a few seconds ago" are identical 99.99% of the time: EC pays 14 ms per read to guarantee a difference that almost never exists. The cost is real and the benefit, for a redirect, is practically null. That is why Enlace is EL.

Exercise 3 — Classify and justify. For each system, give its PACELC class and justify the two branches with one sentence each. (a) A bank's balance system. (b) A social network's post feed. (c) The generation of Enlace's short_code (the write, not the read).

See solution

(a) Bank (balances): PC/EC. if P → it stops rather than allow an overdraft from lack of coordination (consistency over availability). Else → it coordinates on every operation (confirms the balance exactly) even if it costs latency, because money does not tolerate errors. Exactness rules in both branches.
(b) Social network feed: PA/EL. if P → it keeps showing the feed with whatever it has (available). Else → it assembles it from the closest replicas without coordinating (fast), and it does not matter if someone misses seeing a post for a few seconds. Responding always and fast rules.
(c) Generation of the short_code: tends to PC/EC at the critical point. if P → two nodes on either side of a partition must not be able to assign the same code to different URLs (a collision corrupts), so uniqueness requires consistency. Else → generating a unique code may require coordination (or, better, avoiding it by handing out disjoint ranges in advance, like the id_generator of module 3). The key nuance: Enlace is PA/EL on the read (resolve) but needs a stronger guarantee on the uniqueness of the write —that is why it is classified per operation, not with a single label—.

Summary and next step

In this lesson you completed the framework CAP left half-done. With the two branches whose line works you saw the tradeoff CAP ignores: even without a partition, strong consistency costs —because coordinating (confirming every sale by phone) takes time—. PACELC names it with two branches: if Partition, choose A or C; Else, choose Latency or Consistency. You understood why strong consistency costs latency whenever there are replicas (synchronous replication waits for confirmations; asynchronous does not wait but leaves lag), you met the four classes (PA/EL, PC/EC, PA/EC, PC/EL) with real examples, and you classified Enlace as PA/EL: available under partition and low-latency the rest of the time, with the number that justifies it —coordinating would cost 14 ms extra on each of 4,000 reads/s to guarantee something a redirect almost never needs—.

Before moving on you should be able to: read the PACELC sentence and classify a system in its two branches; explain why strong consistency costs latency even without a partition; name the four classes with an example each; and justify why Enlace is PA/EL with its numbers.

What comes next is bringing all of this down to earth. You have decided that Enlace is AP (lesson 4) and EL (this lesson), which in practice goes by a single name: eventual consistency. In lesson 6 you will formalize the difference between strong and eventual consistency, you will see the intermediate spectrum (read-your-writes, monotonic reads) that connects with the replication lag of module 5, and you will measure Enlace's decision with the numbers: how many short_codes are "in flight" at any instant, what probability there is that a read hits a freshly created one, and why the only uncomfortable case —the creator who reads their own link before it propagates— is solved by reading from the primary. It is where the conceptual tradeoff becomes a decision with evidence.

Resources

Daniel Abadi — "Consistency Tradeoffs in Modern Distributed Database System Design" (IEEE Computer, 2012) — the paper that introduced PACELC. Abadi argues why CAP is incomplete and why the latency-vs-consistency tradeoff (the Else) usually matters more in practice than the partition one. The direct source of this lesson; its classification table of real systems is worth the whole paper.
Designing Data-Intensive Applications, Martin Kleppmann — Chapter 5, "Synchronous versus Asynchronous Replication" — the detail of why synchronous replication gives consistency at the cost of latency and asynchronous gives latency at the cost of lag; the concrete mechanism behind the "Else" tradeoff of PACELC.
Abadi — "Problems with CAP, and Yahoo's little known NoSQL system" (blog, 2010) — the blog post where Abadi presented PACELC for the first time, in a more accessible tone than the paper; useful for understanding the motivation with the PNUTS example (a real PC/EL system).

← Previous4. The CAP theorem, explained (without the myth)Next →6. Strong versus eventual consistency, and Enlace's choice