Why is CAP Theorem true?

The CAP Theorem, also known as Brewer's Theorem, is a fundamental principle in distributed systems that states it is impossible for a distributed system to simultaneously provide all three of the following guarantees: Consistency, Availability, and Partition Tolerance. The theorem was first introduced by Eric Brewer in 2000 and later formally proven by Seth Gilbert and Nancy Lynch in 2002.

Why is CAP Theorem True?

To understand why the CAP Theorem is true, let's break down the three properties it addresses:

1. Consistency (C): Every read receives the most recent write or an error. This means that all nodes in the system have the same data at any given time.
2. Availability (A): Every request (read or write) receives a response, without guarantees about the data's consistency across all nodes.
3. Partition Tolerance (P): The system continues to function and provide responses despite network partitions or communication failures between nodes.

The CAP Theorem asserts that in the presence of a network partition (P), a distributed system must choose between ensuring consistency (C) or ensuring availability (A). This is because a network partition divides the system into isolated sub-systems that cannot communicate with each other, forcing a trade-off between consistency and availability.

Proof Sketch

Consider a simple distributed system with two nodes, $$G_1$$ and $$G_2$$, and a client that can send read and write requests to either node. Initially, both nodes have the same value for a variable $$v$$.

1. Network Partition: Suppose a network partition occurs, isolating $$G_1$$ from $$G_2$$. The client sends a write request to $$G_1$$ to update $$v$$ to a new value $$v_1$$. Since $$G_1$$ cannot communicate with $$G_2$$ due to the partition, $$G_2$$ still holds the old value $$v_0$$.

2. Consistency vs. Availability:

   • If the system prioritizes consistency (CP system), $$G_1$$ must ensure that $$G_2$$ also updates $$v$$ to $$v_1$$ before acknowledging the write. However, due to the partition, $$G_1$$ cannot communicate with $$G_2$$, so it cannot guarantee consistency. Therefore, $$G_1$$ must either delay the response (making the system unavailable) or return an error.
   • If the system prioritizes availability (AP system), $$G_1$$ will acknowledge the write immediately, and the client can continue to read and write to $$G_1$$. However, $$G_2$...