What is an impossibility result
An impossibility result proves that no algorithm can simultaneously satisfy a particular collection of properties.
- This tells us some good thing is impossible.
We have already seen:
- SNOW: (S+N+O+W) is impossible;
- NOCS: (N+O+C+S) is impossible.
We add CAP Theorem, PRAM Theorem, and FLP.
CAP Theorem
C: Consistency means linearizability
A: Availability
Every request received by a non-failing node must eventually receive a valid response.
In other words, services must be always available.
P: Partitions
A partition divides the replicas into disconnected components:
Component 1 Component 2
Client 1 → R1 ✕ R2 ← Client 2
↑
messages do not cross
Partition tolerance means the required correctness properties must continue to hold even when messages between the components are lost.
CAP Theorem Proof
As shown in the diagram, replicas cannot guarantee consistency while data partition is present although the system may still be available with partitioned data.
Correct Interpretation of CAP
Partition tolerance is not an optimal feature
In a geo-distributed system, the network can partition regardless of what the designer wants.
Therefore, you cannot configure the physical world with:
partition_tolerance = false
If communication fails, the partition exists. The actual choice during that partition is:
Consistency or Availability
CP: Choose consistency
To preserve linearizability, at least one side must stop serving some operations.
For example, in Raft:
- the side containing a majority may continue;
- the minority side cannot commit writes;
- requests to the minority may block or fail.
This sacrifices availability but preserves consistency.
AP: Choose availability
Every partition continues accepting operations.
The replicas may temporarily diverge:
Left partition: x = 1
Right partition: x = 2
After communication is restored, the system reconciles the versions.
This sacrifices linearizability during the partition while preserving availability.
When there is no partition
CAP does not say that consistency and availability can never coexist.
A system may provide both during normal operation. The unavoidable tradeoff arises when communication is actually disrupted:
During a partition, a replicated system cannot guarantee both linearizability and a response from every non-failing replica.
Can we “beat” CAP by making partitions rare?
No.
A system may:
- use highly reliable links;
- deploy redundant network paths;
- keep replicas geographically close;
- accept unavailability during rare partitions.
That can be an excellent engineering decision, but the theorem still applies when a partition occurs.
PRAM Theorem
PRAM Theorem states:
It is impossible for sequentially consistent system to always provide low latency
Sharding vs Replication
Replication dimension
Moving horizontally means examining copies of the same data at different machines or datacenters.
Relevant impossibilities:
- CAP;
- PRAM.
The central problem is keeping copies of the same object consistent across network distance or failures.
Sharding dimension
Moving vertically means accessing different subsets of data stored on different machines.
Relevant impossibilities:
- SNOW;
- NOCS/PORT.
The central problem is producing one consistent view across distinct shards.
Real systems have both
A production database is usually both:
- sharded for capacity and throughput;
- replicated for durability and availability.
Therefore it is subject to both families of constraints.
For example, a read-only transaction across three Spanner shards may involve:
- choosing a replica for each shard (CAP and PRAM)
- handling replication consistency inside each shard (CAP and PRAM)
- constructing a transactionally consistent view across shards. (SNOW and NOCS)
CAP, PRAM, PORT, SNOW on Consistency Hierarchy
CAP
CAP target linearizability.
To preserve availability during partitions, the system generally has to move below real-time consistency.
PRAM (fill in when needed)
PORT and SNOW
SNOW and NOCS target strict serializability for multi-object transactions.
They show that strict transactional consistency cannot be combined with:
- SNOW’s ideal read latency plus conflicting writes;
- NOCS’s ideal read performance.
FLP (fill in when needed)
Complete Comparison
| Result | System dimension | Impossible ideal | Fundamental tradeoff |
|---|---|---|---|
| CAP | Replication | Linearizable, available, partition-tolerant service | Consistency vs availability during partitions |
| PRAM | Replication | Sequential consistency with both reads and writes always below network delay | Consistency vs operation latency |
| SNOW | Sharding | (S+N+O+W) read-only transactions | Strong guarantees vs optimal read latency |
| NOCS | Sharding | (N+O+C+S) read-only transactions | Strict serializability vs optimal latency and throughput |
| FLP | Consensus | Deterministic, always-terminating consensus with one possible crash in full asynchrony | Guaranteed termination vs asynchronous fault tolerance |