CAP Theorem

Overview

The CAP Theorem (Brewer, 2000) states that a distributed data store can provide at most two of three guarantees simultaneously: Consistency (every read returns the most recent write or an error), Availability (every request receives a non-error response), and Partition Tolerance (the system continues operating when network partitions occur). Since partitions are unavoidable in real networks, systems must choose between consistency and availability during a partition.

Origin

Conjectured by Eric Brewer at PODC 2000 and formally proved by Gilbert and Lynch in 2002. The PACELC theorem (Abadi, 2010) extends CAP: even without partitions, there is a trade-off between latency and consistency.

Examples

# CP system: ZooKeeper, etcd, Consul
# During a partition, refuses writes to preserve consistency
# Used for: leader election, distributed locks, service discovery

# AP system: Cassandra, DynamoDB (default)
# During a partition, accepts writes to all reachable nodes
# Nodes reconcile with last-write-wins or vector clocks after partition heals
# Used for: shopping carts, user sessions, metrics aggregation

# Choosing consistency level per-operation in Cassandra:
# db.execute("INSERT ...", consistency: :quorum)   # CP-ish: requires majority
# db.execute("INSERT ...", consistency: :one)      # AP-ish: single node write

Use Cases

• 01Choosing a database: Redis Sentinel (CP), Cassandra (AP), PostgreSQL with read replicas (CP with lag)
• 02Designing conflict resolution: AP systems need strategies for merging diverged state (LWW, CRDTs, application-level merge)
• 03Setting consistency levels per operation: financial transactions need quorum; analytics writes can tolerate one

When Not to Use

• //CAP is not a direct operational decision, it describes unavoidable trade-offs, not implementation choices

Technical Notes

• CAP is often misunderstood as a menu. You do not "pick two" at design time, partitions happen at runtime, and when they do, your system's behaviour determines its classification
• PACELC: when no partition (E): choose between Latency (L) and Consistency (C). PostgreSQL synchronous replication = high consistency + higher latency
• CRDTs (Conflict-free Replicated Data Types) are data structures designed for AP systems: merge semantics are built into the type so conflicts resolve automatically
• Many modern databases offer tunable consistency (DynamoDB, Cassandra, MongoDB), you choose CP or AP at the query level