CAP Theorem

CAP Theorem

The CAP theorem (Brewer's theorem, 2000) states that a distributed data store can provide at most two out of three guarantees simultaneously:

• Consistency (C): Every read receives the most recent write or an error. All nodes see the same data at the same time.
• Availability (A): Every request receives a non-error response, without guaranteeing it reflects the most recent write.
• Partition Tolerance (P): The system continues to operate despite arbitrary message loss or failure between nodes.

Why You Can Only Pick Two

In any real network, partitions will happen — cables get cut, switches fail, packets get lost. So partition tolerance is not optional. This means the real choice is between CP and AP:

         C
        / \
       /   \
     CP     CA ← only possible if no partitions (single datacenter)
     /       \
    P ─── AP ─ A

Proof intuition: Suppose nodes A and B are partitioned. A client writes value v2 to node A. Another client reads from node B.

• If we guarantee consistency, B must return v2, but B cannot reach A → we must reject the read (sacrifice availability) → CP.
• If we guarantee availability, B must respond, but it only has stale v1 → we sacrifice consistency → AP.
• You cannot have both during a partition.

Real-World Systems

Your Task

Implement a CAPSimulator class that models a two-node distributed system. It should:

• Store a value on each node (nodeA, nodeB).
• Support write(value) which writes to node A. If not partitioned, it replicates to node B.
• Support read(node) which returns the value at the given node — but behavior depends on the mode:
  • In "cp" mode: during a partition, reading from node B throws an error (consistency over availability).
  • In "ap" mode: during a partition, reading from node B returns its (possibly stale) value (availability over consistency).
• partition() and heal() toggle the network partition. When healed, node B syncs to node A's value.