Partition Tolerance (CAP)

When the network splits our nodes, we keep serving. The remaining choice: consistency or availability — not both.

Problem

Every distributed system eventually experiences network partitions: inter-DC cable failure, congestion, switch upgrade. During a partition, two cluster halves can no longer synchronise. Brewer's CAP theorem (PODC keynote 2000) states one must choose: strong consistency (every read sees the latest write) or availability (every request gets a response) — not both when P holds.

Forces

• Network partitions exist in production, regardless of infrastructure care.
• Refusing writes during a partition (CP) freezes minority-side users.
• Accepting writes everywhere (AP) creates conflicts to reconcile.
• Inter-DC latency (ms to 10s) shapes the practical decision: it's PACELC more than CAP.
• Kleppmann (2015) critiques CAP: "C" is not serializability, "A" assumes infinite timeout; the 2x2 matrix oversimplifies.

Solution

Explicitly design the system's response under partition: CP (Spanner, CockroachDB, HBase, etcd) suspends writes on the minority to preserve linearizable consistency; AP (Cassandra, Dynamo, Riak) accepts writes everywhere and reconciles later (CRDTs, last-write-wins, vector clocks). The choice depends on business: a banking system prefers CP, a shopping cart prefers AP. A modern variant (PACELC, Abadi 2012) adds the latency/consistency trade-off in the absence of partition.

Structure

Cluster intact (P=0):
  Writes commit on majority → C and A both hold

Network partition splits cluster into {A,B} | {C,D,E}:

  CP design (Raft, Spanner):
    Side {A,B}  ──► reject writes (no quorum)
    Side {C,D,E}──► accept writes (has quorum)
    On heal: side {A,B} catches up the log
    => no divergence, but partial unavailability

  AP design (Dynamo, Cassandra):
    Side {A,B}  ──► accept writes locally
    Side {C,D,E}──► accept writes locally
    On heal: conflict resolution (LWW or CRDT)
    => always available, may surface stale reads

EDI implementation

A multi-region EDI hub must choose, on a transatlantic partition between Europe and US DCs: (a) CP — suspend writes on the US side, US orders queue locally until link recovery (RPO 0, RTO ~minutes); (b) AP — each DC keeps receiving orders; on link recovery, reconcile. The usual EDI rule is CP for invoicing (strict fiscal consistency) and AP for shipment tracking (tracking data has no global uniqueness constraint).

Anti-patterns

• Claiming to do CA — a false promise; any partition forces CP or AP.
• Default CAP choice without business analysis — incidents misunderstood in production.
• Believing CAP ends the debate — PACELC adds latency vs consistency under normal operation.
• Mixing CP and AP semantics in the same system without making it explicit — chaos on partition.
• Chaos tests without partition tests — resilience is not validated.

Related patterns

• Consensus (Raft) — typical CP choice.
• Sharding — limits partition scope to subsets.
• Circuit Breaker — protection mechanism under partition.
• Bulkhead — isolates pools to reduce partition impact.

Sources

• Brewer E. — Towards Robust Distributed Systems, PODC keynote 2000.
• Kleppmann M. — Please stop calling databases CP or AP, 2015. martin.kleppmann.com — Please stop calling databases CP or AP
• Abadi D. — Consistency Tradeoffs in Modern Distributed Database System Design, IEEE Computer 2012 (PACELC).
• Kleppmann M. — Designing Data-Intensive Applications, O'Reilly 2017, ch. 8 "The Trouble with Distributed Systems", ch. 9.