CAP Theorem Part 4: The relationship between Consistency, Availability, and Partition Tolerance

This is the fourth of a six part blog post about the CAP Theorem. You can read the first part here. You can download all six parts in one document here.

Relationship between T_C, T_A, and T_P

Assertion

We assert that in a service as described in the previous post,
TC + TA ≥ TP
In other words, a distributed service that guarantees T_C Consistency, and guarantees a response in less than T^A, cannot tolerate network partitions lasting longer than (T_C + T_A).

Proof

The proof of the assertion is provided by contradiction. Assume for the purposes of this proof that,

T_P > T_C + T_A

In other words we assume that a distributed service that guarantees results that are T_C Consistent, and guarantees a response in less than T_A, can tolerate network partitions lasting longer than (T_C + T_A).

We show that this is impossible.

Consider the figure above depicting the period of time T_P during which some two nodes (n_A and n_B) in the service were unable to communicate with each other. As depicted in the figure, the network partition begins at T_START and lasts for duration T_P.

As T_C + T_A < T_P, we should be able to find a time ‘t’ such that:

• T_START < t < T_START + T_P, and
• T_START < t + T_C + T_A < T_START + T_P.

In other words, the interval of time [t, t + T_C + T_A] must lie entirely within [T_START, T_START + T_P], the interval when the nodes n_A and n_B are unable to communicate with each other.

Consider further that at some point of time in the interval [T_START, t], a request (R1) is received by node n_A, and a request (R2) is received by node n_B at time t + T_C.

As T_C + T_A < T_P, the node n_B should be able to respond to the request R2 before the end of the network partition and that response would be T_C­ Consistent.

In order for this to be possible, the effect of the request R1 processed by n_A must have been propagated to n_B before the end of the network partition between n_A and n_B, and that is a contradiction as no messages from n_A could have made it to n_B before during the partition.

We therefore conclude that

T_C + T_A ≥ T_P,

or a distributed service that guarantees T_C Consistency, and guarantees a response in less than T_A, cannot tolerate network partitions lasting longer than (T_C + T_A).