The CAP Theorem: Choose per Operation, Not per Database

By Sergey Nosov

15 October 2026

On 21 October 2018, routine maintenance on failing optical equipment cut the link between GitHub’s primary US East Coast data center and its East Coast network hub. The link came back in 43 seconds. GitHub’s service stayed degraded for 24 hours and 11 minutes.

GitHub managed failover for its MySQL databases with Orchestrator, a tool built on the Raft consensus algorithm. During the partition, the Orchestrator nodes that could still reach one another formed a quorum and began moving the primary databases to the West Coast. Raft kept those nodes in agreement, but MySQL replicated the data separately: the East Coast primaries held a few seconds of writes that had not reached the West.

When the link returned, applications began writing to the new primaries. Each side now held writes the other lacked, so GitHub could not safely fail back to the East. It kept the West Coast primaries and rebuilt the East Coast databases from backups, although applications in the East now crossed the country for most of their database calls. Its post-incident analysis says they could not cope with the added latency but judges that “the extended degradation of service was worth ensuring the consistency of our users’ data.”

A partition is where consistency and availability collide. The failover kept the databases writable, but because replication lagged, it cost consistency. That choice had been made in advance: Orchestrator behaved as configured, and the first fix the analysis listed was to stop it from promoting primaries across regions. And the cross-country latency, which GitHub called “a major contributing factor,” is a cost the CAP theorem ignores.

The moment data lives in more than one place, the network becomes part of the correctness story. This article argues that the choice between answering and refusing belongs to each operation, not to the database, and should be made deliberately and in advance, in configuration and code. Its examples were tested on Apache Cassandra 5.0.9 with version 4.9.0 of the Cassandra driver for Node.js.

What the Theorem Says

Eric Brewer, a professor at the University of California, Berkeley, and a cofounder of Inktomi, proposed the theorem as a conjecture. In a 2012 retrospective, he recalled that the theorem “first appeared in fall 1998. It was published in 1999 and in the keynote address at the 2000 Symposium on Principles of Distributed Computing, which led to its proof.” The keynote slide named consistency, availability, and tolerance to network partitions, then read: “You can have at most two of these properties for any shared-data system.”

In 2002, Seth Gilbert and Nancy Lynch of MIT proved the conjecture. Their definitions are narrower than everyday usage:

Over such a network, no system can guarantee both consistency and availability. The proof fits in a paragraph. Split the nodes into two groups and lose every message between them. A client writes a new value in one group; later, another client reads in the other. Availability says the read must return something. The second group knows only the old value, and consistency forbids returning it.

Two details matter later. First, CAP’s availability sets no deadline. Gilbert and Lynch note that it “puts no bound on how long the algorithm may run before terminating,” so a database that answers after 2 minutes counts as available. That is not the uptime of a service-level agreement, which my article on availability by the numbers covers. Second, Brewer points out that the C in CAP is single-copy consistency. The C in ACID is a broader idea: preserving database rules such as unique keys.

What a Partition Forces

Brewer’s own explanation is the shortest:

The easiest way to understand CAP is to think of two nodes on opposite sides of a partition. Allowing at least one node to update state will cause the nodes to become inconsistent, thus forfeiting C. Likewise, if the choice is to preserve consistency, one side of the partition must act as if it is unavailable, thus forfeiting A.

Giving up partition tolerance is not a real option for a system that spans a network. In 2010, Daniel Abadi asked what a system that is “not tolerant” of partitions does when one happens anyway. It loses availability, which makes CA and CP “essentially identical.” Brewer later suggested treating CA as a bet that a partition is far less likely than other systemic failures, such as disasters or several simultaneous faults.

So during a partition, each operation either refuses or answers. Designs that forfeit consistency keep answering on both sides and reconcile afterward, with last-writer-wins timestamps, version vectors, or data types built to merge, known as CRDTs. The classic example comes from Werner Vogels of Amazon: the shopping cart uses “a write-always system,” and the carts are merged after the partition heals.

In Brewer’s words, “the essence of CAP takes place during a timeout.” At that moment, the program must either “cancel the operation and thus decrease availability, or proceed with the operation and thus risk inconsistency.” Waiting longer only postpones the decision: “retrying communication indefinitely is in essence choosing C over A.” MongoDB documents that behavior: a write whose write concern cannot be met blocks indefinitely unless the client sets a timeout.

A Partition on a Real Cluster

The test cluster runs three Cassandra nodes in containers, in a data center named dc1, and this keyspace keeps a copy of every row on all three:

CREATE KEYSPACE auth
WITH replication = {
  'class': 'NetworkTopologyStrategy',
  'dc1': 3
};

CREATE TABLE auth.revoked_tokens (
  token_id   text PRIMARY KEY,
  revoked_at timestamp
);

To create a partition, the third node is disconnected from the container network. It keeps running and answering its own clients but cannot reach the other two. On the majority side, a client revokes a token in cqlsh, Cassandra’s shell:

CONSISTENCY QUORUM;
INSERT INTO auth.revoked_tokens
  (token_id, revoked_at)
VALUES ('t-123', toTimestamp(now()));

The write succeeds. QUORUM requires a majority of the replicas, and two of the three acknowledged it. Then a client of the isolated node asks whether the token is revoked, first at QUORUM:

CONSISTENCY QUORUM;
SELECT token_id
FROM auth.revoked_tokens
WHERE token_id = 't-123';

The node refuses. Here is the heart of the error, trimmed and wrapped:

... code=1000 [Unavailable
exception] message="Cannot achieve
consistency level QUORUM" ...

That is the consistency side of the trade-off: no answer rather than a possibly stale one, although QUORUM alone does not make Cassandra linearizable. The same question at ONE gets an answer:

CONSISTENCY ONE;
SELECT token_id
FROM auth.revoked_tokens
WHERE token_id = 't-123';
Consistency level set to ONE.

 token_id
----------


(0 rows)

The isolated node has not received the revocation, so a service that trusted this answer would accept the revoked token. That is the availability side. One cluster offered both trade-offs during one partition, and the consistency level of each statement chose between them.

The isolated node also accepted writes at ONE while refusing them at QUORUM. On the majority side, a QUORUM write changed a setting from blue to green. On the isolated node, a client that still read blue at ONE changed it to red about 6 seconds later. Until the partition healed, a QUORUM read on the majority side still returned green.

After the partition healed, a QUORUM read returned red, because Cassandra keeps the write with the later timestamp. The client that wrote red never saw green, so its change silently replaced one it did not know about. In this short test, the isolated node also caught up, returning the revoked token at ONE. Cassandra describes its catch-up mechanisms, hints and read repair, as best effort; its guarantee of eventual consistency rests on anti-entropy repair.

Five Misreadings

“Pick any two of three.” Brewer wrote in 2012 that the two-of-three formulation “was always misleading because it tended to oversimplify the tensions among properties.” The theorem rules out something narrow: perfect availability and consistency during a partition.

“An AP system is always inconsistent.” CAP constrains behavior only during a partition. Abadi points out that without a partition, CAP allows full ACID guarantees alongside high availability. Many systems that choose availability do give up consistency all the time, but he attributes that to latency, not to CAP. PACELC, below, covers that.

“CP means downtime.” Only where there is no quorum. If no side of a partition holds a majority, a quorum-based operation stops everywhere. Otherwise it keeps working on the majority side and stops on the others. Writing about Google’s Spanner in 2017, Brewer called that the most likely outcome: “one side has a quorum and will continue on just fine, perhaps after electing some new leaders.” Kleppmann adds that if all clients can be shifted to that side, “the clients will in fact see no downtime at all.”

“CAP covers latency.” It does not. In Kleppmann’s words, CAP-available systems “are allowed to be arbitrarily slow to respond.” Brewer wrote in 2012 that the classic interpretation of CAP ignores latency, although “in practice, latency and partitions are deeply related.”

“A database is CP or AP.” In 2015, Kleppmann went through several popular databases and could not put one cleanly in either bucket. He concluded that CP and AP “are simply not the right labels to describe systems,” because one piece of software can offer operations with different consistency characteristics. Brewer had made the same point in 2012: the choice “can change according to the operation or even the specific data or user involved.”

Labels Belong to Operations

Popular distributed stores expose the choice as settings, often per request. A label describes a default, and sometimes not even that:

PACELC: The Trade-Off without a Partition

CAP describes the rare moments when the network splits. Abadi argued that a second trade-off, between latency and consistency, has shaped database design more. He first proposed PACELC, pronounced “pass-elk,” on his blog on 23 April 2010 and published it in IEEE’s Computer magazine in February 2012. The paper puts it this way:

If there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?

The reason is replication. As soon as a database keeps copies, a consistent answer needs the copies to coordinate, and coordination takes time. Abadi called ignoring this trade-off a major oversight. It is “present at all times during system operation, whereas CAP is only relevant in the arguably rare case of a network partition.”

The paper classified the systems of 2012 on both halves. The default versions of Dynamo, Cassandra, and Riak were PA/EL: they gave up consistency for availability during a partition and for lower latency the rest of the time. Fully ACID systems such as VoltDB and Megastore, along with BigTable and HBase, were PC/EC. MongoDB, as it worked then, was PA/EC, although Abadi noted that its minority side was not CAP-available. Those labels have aged: MongoDB’s default write concern is now majority.

Microsoft publishes the price of the EC side for Cosmos DB. With strong consistency across regions, the write latency is “two times round-trip time (RTT) between any of the two farthest regions, plus 10 milliseconds at the 99th percentile.” Microsoft blocks strong consistency by default for accounts whose regions span more than 8,000 kilometers. Even Spanner, with GPS receivers and atomic clocks behind TrueTime, “slows down to wait out that uncertainty” when the clocks’ uncertainty is large. As Brewer wrote, Google’s network “cannot improve the speed of light.”

At the extreme, latency and availability blur. Abadi noted that “availability and latency are arguably the same thing: an unavailable system essentially provides extremely high latency.” That is the GitHub incident again. The West Coast primaries were reachable, yet a cross-country round trip on most database calls made the site, in GitHub’s words, “unusable for many users.”

Consistency Is a Spectrum

Jepsen, which tests databases against their consistency claims, publishes a guide to consistency models that says which ones can stay available during a partition. Its verdicts, plus Vogels’s definition of eventual consistency, show the trade-off:

There is useful room below linearizability. Session guarantees such as read your writes avoid global coordination. But the client must carry session state or stay with one server, and a lagging replica must be waited for or skipped. My article on CQRS implements read your writes by waiting for a read model to catch up. It gives up with an error after 2 seconds, a small CAP decision of its own.

Doug Terry’s 2011 Microsoft Research report makes the case for the middle of the spectrum with a baseball game. Its verdict: “Eventual consistency is insufficient for most of the participants, but strong consistency is not needed either.”

What W + R > N Buys

In Dynamo-style stores such as Cassandra, tunable consistency comes down to arithmetic. Each item lives on N replicas; a write waits for W acknowledgments and a read for R responses. Vogels gave the rule in 2008: “If W+R > N, then the write set and the read set always overlap and one can guarantee strong consistency.” QUORUM is a majority of the replicas, so with three replicas it is two, and 2 + 2 > 3.

My article on combinatorics in software engineering shows why the two groups must overlap, and why Dynamo’s sloppy quorums can still miss a write. The overlap assumes that both groups come from the same N replicas: two LOCAL_QUORUM operations in different data centers need not overlap. The guarantee is real, but it is smaller than “strong consistency” suggests:

The Security Lens: The Attacker Picks the Partition

For a security-minded team, the CAP and PACELC choice maps directly to risk. Revocation lists, authorization data, and secrets lean toward consistency, because stale data there can be a security incident. Audit-log ingest, security information and event management (SIEM) event streams, and telemetry lean toward availability, because there the bigger risk is losing events.

One difference from ordinary failures changes the analysis: an attacker who interferes with the network can cause the partition. Browsers learned this with certificate revocation. A browser cannot always reach the certificate authority’s revocation service, so browsers effectively ignored checks that failed with a network error, a behavior called soft-fail.

In a 2012 post about Chrome, Adam Langley spelled out the consequence. An attacker “who can intercept HTTPS connections can also make online revocation checks appear to fail and so bypass the revocation checks!” His verdict: “soft-fail revocation checks are like a seat-belt that snaps when you crash.” Chrome’s answer was to push a list of revoked certificates, which an attacker would have to block “constantly, from the time of revocation.”

Identity systems face the same trade-off. AWS documents that IAM “uses a distributed computing model called eventual consistency.” It asks customers to verify that a change has propagated before production workflows depend on it, without promising a maximum delay.

Microsoft Entra issues access tokens valid for 1 hour by default to clients without continuous access evaluation (CAE). Microsoft found that shorter lifetimes, a “blunt object,” hurt user experience and reliability “without eliminating risks.” With CAE, supported services subscribe to critical events, such as a disabled account. Microsoft aims for “near real time” but says event propagation can take up to 15 minutes. In CAE sessions, tokens can live up to 28 hours, because events and policy evaluation, not just expiry, drive revocation. Policy and group-membership changes can take up to a day.

So leaning toward consistency is not one setting but a set of decisions about the revocation path:

Brewer’s automated teller machine example takes the other path: stay available, but bound the risk. During a partition, “modern ATMs limit the net withdrawal to at most k, where k might be $200.”

In code, each statement carries its own consistency level. The Node.js module below checks revocations and writes telemetry to app.metrics, a table in a second keyspace replicated like auth, with (device_id, ts) as its primary key:

import cassandra from "cassandra-driver";

const { quorum, one } =
  cassandra.types.consistencies;

const client = new cassandra.Client({
  contactPoints: ["127.0.0.1"],
  localDataCenter: "dc1",
  // Each request: 2 s, not 12
  socketOptions: {
    readTimeout: 2000,
  },
});

const CHECK_REVOKED =
  "SELECT token_id " +
  "FROM auth.revoked_tokens " +
  "WHERE token_id = ?";

// Security: QUORUM, fail closed
async function isRevoked(tokenId) {
  try {
    const rs = await client.execute(
      CHECK_REVOKED, [tokenId], {
        prepare: true,
        consistency: quorum,
      });
    return rs.rowLength > 0;
  } catch (err) {
    // Unknown: treat as revoked
    console.warn(err.message);
    return true;
  }
}

const RECORD_METRIC =
  "INSERT INTO app.metrics " +
  "(device_id, ts, value) " +
  "VALUES (?, ?, ?)";

// Telemetry: one replica will do
async function recordMetric(
  deviceId, ts, value) {
  await client.execute(RECORD_METRIC,
    [deviceId, ts, value], {
      prepare: true,
      consistency: one,
      isIdempotent: true,
    });
}

export { isRevoked, recordMetric };

A statement without a consistency level gets the driver’s default, LOCAL_ONE for a self-managed cluster, so a revocation check written that way has already chosen availability. The client gives each request 2 seconds instead of the driver’s default of 12. In testing, a timeout set on the statement alone missed the first call, which must also prepare the statement.

On the isolated node, the QUORUM lookup failed with “Not enough replicas available for query at consistency QUORUM (2 required but only 1 alive),” and isRevoked returned true. When that node was also frozen and could not answer at all, the check gave up after 2 seconds and returned true again. Every token checked there would be refused, revoked or not. The same lookup at ONE found no rows. recordMetric succeeded at ONE, and writing the same event twice left one row.

The function checks revocation only. Signature, expiry, and authorization checks stay separate, and every path that accepts a token must await it.

Audit and telemetry run the other way. A SIEM event that arrives 200 milliseconds late is fine; one that is dropped because the store was unavailable is not. Keep ingestion available, but do not mistake an acknowledgment from one replica for safety: if that replica is lost before the write reaches the others, the event is gone.

Queue events durably until the store confirms them at the level the audit trail needs, and move them off the host promptly. Give each event a stable identifier and keep it across retries. In recordMetric, the device and the event’s own time form the key, so a retried write lands in the same row; audit events need a real event ID. Watch the buffers, too. During its recovery, GitHub “processed ~200,000 webhook payloads that had outlived an internal TTL and were dropped.” Late became lost.

A Checklist for Each Data Path

The CAP and PACELC entries in my Software Development Principles series list warning signs, such as engineers who cannot say what happens during a network split. Asking these questions for each kind of data keeps the choice deliberate:

CAP is not a label to put on a database. It is a question to ask of every operation, before the network splits: when this replica cannot reach the others, should it answer or refuse? PACELC adds the everyday question: when it can reach them, how long may the answer take?

Further Reading