CAP Theorem: First Principles, the ‘2 of 3’ Myth, and How Google Spanner Approaches It

The CAP theorem is one of the most widely cited yet frequently misunderstood concepts in distributed systems design. Colloquially introduced by Eric Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC) and formally proven by Seth Gilbert and Nancy Lynch in 2002, the theorem is often oversimplified as a pick-two-out-of-three rule: Consistency, Availability, and Partition Tolerance.

In practice, this oversimplification leads engineers to make flawed architectural assumptions. By examining the theorem from first principles—and exploring Eric Brewer’s own reflections alongside Google Spanner’s implementation—we can understand what CAP actually guarantees, what it forbids, and how modern global databases operate under its constraints.

---

1. Deconstructing the Acronym from First Principles

To understand CAP, one must set aside loose colloquial definitions and look at the formal specifications of its three properties.

               +-----------------------+
               | Partition Tolerance   |
               |      (Network P)      |
               +-----------+-----------+
                          / \
                         /   \
       Network Split    /     \   Network Split
       Forces CP       /       \  Forces AP
                      /         \
                     /           \
  +-----------------+             +------------------+
  |   Consistency   |-------------|   Availability   |
  |   (Linearizable)|  In Absence |  (Non-Error Resp)|
  +-----------------+ of Partition+------------------+
                       (CA Mode)

Consistency ($C$): Linearizability

In the CAP theorem, Consistency means linearizability (or single-copy serializability of operations). Specifically:

Every read request receives the most recent write or an error.

Crucial Distinction: CAP Consistency vs. ACID Consistency

• ACID Consistency ($C_{ACID}$): An application-defined invariant. It guarantees that a transaction transitions a database from one valid state to another valid state, upholding schema rules, primary key constraints, foreign keys, and triggers. If a transaction violates a constraint, it is aborted.
• CAP Consistency ($C_{CAP}$): A distributed systems freshness and ordering guarantee. It guarantees that all nodes see the same state at the same time. Once a write has been acknowledged, any subsequent read across any node must observe that update or fail entirely.

Availability ($A$): Non-Error Responses

Availability in the CAP context has a strict mathematical definition that differs from standard SLA/uptime metrics:

Every non-failing node must return a non-error response for every request it receives, without the guarantee that it contains the most recent write.

Key nuances:

• It does not mean 99.999% uptime.
• Returning an HTTP 500, a connection timeout, or an explicit rejection error means the operation was not available in the CAP sense.
• The response does not have to be fresh; it only has to be successful and processed.

Partition Tolerance ($P$): Network Realities

Partition tolerance is not an optional feature you can choose to enable or disable. It describes a system’s ability to handle network anomalies:

The system continues to operate despite an arbitrary number of messages being dropped, delayed, or partitioned by the network between nodes.

In any distributed architecture communicating over physical networks (switches, routers, optical fibers), packets can and will be dropped or delayed. A network partition occurs when a cluster of nodes is split into two or more disjoint groups that cannot communicate with each other.

---

2. Debunking the “Pick Two Out of Three” Fallacy

The traditional mental model suggests that a designer can sit down and choose:

• CA: Consistent and Available (ignoring Partitions).
• CP: Consistent and Partition Tolerant (sacrificing Availability).
• AP: Available and Partition Tolerant (sacrificing Consistency).

This trilemma is misleading. You cannot “choose” CA in a distributed system because network partitions are an unavoidable property of distributed hardware.

The Real Formulation of CAP

In reality, the CAP theorem states:

In the absence of network partitions, a distributed system can provide both Consistency and Availability (CA). However, when a network partition inevitably occurs, the system must choose between Consistency (CP) or Availability (AP).

graph TD
    A[Normal Network Operation] -->|No Partitions| B[Achieve Consistency + Availability]
    A -->|Network Split Occurs| C{Must Choose Strategy}
    C -->|Strategy 1: Abort / Error| D[CP: Preserve Consistency, Sacrifice Availability]
    C -->|Strategy 2: Serve Stale Data| E[AP: Preserve Availability, Sacrifice Consistency]

What Happens During a Partition?

Consider a distributed system partitioned into two segments: Subnet $\alpha$ and Subnet $\beta$.

1. A client issues a write to Subnet $\alpha$.
2. Subnet $\alpha$ updates its local state. However, because the connection between $\alpha$ and $\beta$ is severed, $\alpha$ cannot replicate this write to $\beta$.
3. A second client issues a read for the same record to Subnet $\beta$.

Now, the system has only two viable choices:

• Option 1 (CP - Consistency Chosen): Subnet $\beta$ recognizes that it cannot contact $\alpha$ to verify whether it holds the latest write. To prevent returning stale data, it returns an error or times out. Availability is forfeited to maintain linearizability.
• Option 2 (AP - Availability Chosen): Subnet $\beta$ processes the read and returns whatever version it currently has. The client gets a valid, non-error response, but the data is stale. Consistency is forfeited to maintain availability.

Single-Node Systems and CA

A single-node instance of MySQL or PostgreSQL is sometimes labeled as “CA.” While it does not experience inter-node network partitions ($P$ does not apply), if the host server crashes, the database is 100% unavailable. A single-node system avoids partitions by definition, but it cannot achieve distributed fault tolerance.

---

3. Quorums and Partition Dynamics

Most modern distributed databases use consensus mechanisms (such as Paxos or Raft) with quorum-based read and write replication to handle partitions dynamically.

Assume a cluster with $N = 5$ replicas. To safely commit a write or read, a operation must achieve a majority quorum:

$Q = \left\lfloor \frac{N}{2} \right\rfloor + 1 = 3$

+-------------------------------------------------------------+
|                        NETWORK SPLIT                        |
|                                                             |
|  +----------+   +----------+   |   +----------+ +---------+ |
|  |  Node 1  |   |  Node 2  |   |   |  Node 4  | |  Node 5 | |
|  +----------+   +----------+   |   +----------+ +---------+ |
|         \           /          |          \         /       |
|          +---------+           |           +-------+        |
|          | Node 3  |           |                            |
|          +---------+           |                            |
|                                |                            |
|         SUB-CLUSTER A          |        SUB-CLUSTER B       |
|       Size = 3 (Majority)      |     Size = 2 (Minority)    |
|       Can Form Quorum (CP)     |    Cannot Form Quorum      |
+-------------------------------------------------------------+

• In Sub-cluster A ($3$ nodes): A majority ($3/5$) can be formed. Writes and linearizable reads succeed.
• In Sub-cluster B ($2$ nodes): A majority cannot be formed.
  • A CP system will reject writes and reads in Sub-cluster B, returning an error to protect data consistency.
  • An AP system will accept writes and reads on Sub-cluster B, creating diverged states (split-brain) that must be reconciled later via vector clocks, Conflict-Free Replicated Data Types (CRDTs), or Last-Write-Wins (LWW) resolution.

---

4. Does Google Cloud Spanner Break the CAP Theorem?

When Google released Cloud Spanner, it was frequently claimed that Spanner broke the CAP theorem by providing global distribution, external consistency (serializability), and five-nines (99.999%) availability.

In 2017, Eric Brewer published a paper addressing this directly: “Spanner: Becoming a CAP-Available System.”

The Direct Answer

Technically, no. Pragmatically, yes.

Brewer clarifies that Spanner does not break the laws of physics or mathematics. If an actual network partition isolates a replica group, Spanner chooses Consistency over Availability—making it technically a CP system.

However, users can safely treat Spanner as a CA system for their application logic because its probability of experiencing an outage due to network partitions is negligible.

                       Is Spanner CP or CA?
                                 |
             +-------------------+-------------------+
             |                                       |
       THEORETICALLY                           PRACTICALLY
             |                                       |
         CP System                               CA System
(If a partition occurs, it              (Runs on redundant private WAN;
chooses C and forfeits A)              partitions cause <10% of rare outages;
                                        users design systems assuming CA)

How Spanner Achieves High Availability in Practice

1. Private, Redundant Physical Infrastructure

Public internet routes rely on commodity BGP peering, where fiber cuts, misconfigurations, and route flaps are common. In contrast, Spanner runs entirely on Google’s private, globally provisioned fiber network.

• Every data center is linked by multiple independent physical fiber paths.
• Google controls the hardware, network routers, and deployment cycles.
• According to Google’s published data, network partitions account for less than 10% of Spanner’s already rare outages.

2. Relaxing 100% Availability to Operational Reality

The formal CAP theorem assumes a strict binary: 100% availability or 0%. In the real world, no software or hardware achieves 100% availability. Hardware failures, human errors, power outages, and software bugs occur regardless of the network.

If Spanner’s overall availability is 99.999% (less than 5.26 minutes of downtime per year), network partitions are an insignificant contributor to user-perceived downtime. Applications can build on top of Spanner without implementing complex partition-handling or eventual consistency logic.

3. Google TrueTime and Synchronized Clocks

Spanner’s external consistency relies on its TrueTime API. Unlike standard Network Time Protocol (NTP), which has millisecond-level drift and unpredictable jitter, TrueTime combines two distinct hardware reference sources:

• GPS receivers with dedicated antennas.
• Atomic clocks (Rubidium oscillators) installed across data centers.

+-----------------------+         +-----------------------+
|     GPS Receivers     |         |     Atomic Clocks     |
+-----------+-----------+         +-----------+-----------+
             \                               /
              \                             /
               +-------------+-------------+
                             |
                             v
                 +-----------------------+
                 |     TrueTime API      |
                 | Returns [earliest,    |
                 |          latest]      |
                 | Uncertainty: ϵ ≤ 7ms  |
                 +-----------+-----------+
                             |
                             v
                 +-----------------------+
                 | Commit Wait Mechanism |
                 | Guarantees Global     |
                 | Causal Ordering       |
                 +-----------------------+

TrueTime represents time as an interval $[t_{earliest}, t_{latest}]$ with a bounded uncertainty $\epsilon$ (typically $\le 7\text{ ms}$).

When a transaction commits, Spanner assigns it a timestamp $t$ and enforces a commit wait: the coordinator waits out the uncertainty window ($2\epsilon$) before releasing the commit to clients. This guarantees that any subsequent transaction anywhere in the world will receive a timestamp strictly greater than $t$, ensuring lock-free, globally consistent snapshot reads across the entire distributed database.

---

5. Offline-First Systems and Long-Lived Partitions

While enterprise systems like Spanner run on private networks to minimize partitions, other architectures must tolerate partitions that last for hours, days, or weeks. Examples include mobile applications, edge devices, and local-first software.

When systems operate disconnected from a central authority:

• Strict Quorum Fails: A mobile device cannot obtain a majority vote against a remote cluster.
• AP Mode is Mandatory: The local client must accept writes and remain available while offline.
• Reconciliation Strategies: When the partition heals, diverging branches must converge.

Resolving Conflicts with CRDTs

In offline-first systems, Conflict-Free Replicated Data Types (CRDTs) provide deterministic eventual consistency without centralized consensus:

• State-based CRDTs (CvRDTs): Nodes exchange full states and merge them using a mathematically proven join-semilattice function (monotonic, associative, commutative, and idempotent).
• Operation-based CRDTs (CmRDTs): Nodes transmit operations over the wire, designed such that concurrent operations commute.

Using CRDTs, even if sub-networks remain disconnected indefinitely, both sides can accept writes independently and guarantee convergence once the network reconnects.

---

6. Summary Comparison: CAP Dimensions Across Systems

System	Primary CAP Class	Mechanism Under Partition	Consistency Model	Infrastructure Reliance
Standalone RDBMS (e.g., Single MySQL)	N/A (Non-Distributed)	Single node failure yields total downtime	Strong / Serializability	Single Host / Shared Disk
Apache Cassandra	AP	Replicas accept local writes; resolves via LWW or Read Repair	Eventual	Commodity Hardware / Public Cloud
Etcd / ZooKeeper	CP	Minority partition rejects operations; requires majority quorum	Linearizable	Private or Public Cloud
Google Cloud Spanner	Practically CA / Technically CP	Aborts/delays operations if quorum cannot be achieved	External Consistency (Serializable)	Redundant Private Fiber + TrueTime (Atomic/GPS)

---

Key Architectural Takeaways

1. Do not view CAP as a menu: You cannot choose CA while ignoring partitions. A distributed system either preserves linearizability by rejecting requests during a network split (CP), or preserves availability by serving potentially stale data (AP).
2. Consistency in CAP is Linearizability: It is entirely distinct from the data validity constraints represented by the ‘C’ in ACID transactions.
3. Network partitions are operational, not theoretical: Outside of high-end private data centers, distributed systems span commodity internet infrastructure where partitions, latency spikes, and packet losses are baseline operational realities.
4. Pragmatic engineering beats strict theory: Google Spanner shows that while you cannot mathematically break the CAP theorem, investing in hardware redundancy, bounded time uncertainty, and controlled network paths can make partition-induced downtime so rare that systems effectively operate with CA characteristics.