-3

In the CAP theorem, there are only three possible cases:

  • C and A without P
  • C and P without A
  • A and P without C

How can we have both P and C in the second case?

Doesn't propagation of update from one replica to the other require a communication path between the two replicas?

  • If network partition happens between two replicas, isn't it impossible to achieve consistency?

  • If the replicas can achieve consistency, how can network partition between the replicas happen?

The current answer says that in presence of network partition between the replica nodes, the system can stay in consistency, by not responding.

  • The data stored in the replicas are still not in consistency. Does Consistency mean consistency between the data stored in the replicas, or between the responses from the replica nodes?

  • How does a replica node know whether network partition happens or the other replica nodes are crashed? In the latter case, it shouldn't stop responding.

Thanks.

3

The CAP Theorem says that you can only achieve at maximum two out of the three properties of Consistency (every read receives the most recent write or an error), Availability (every read receives a write, but not necessarily the most recent one), and Partition Tolerance (the system keeps responding when an arbitrary amount of messages between the nodes are dropped or delayed). So, according to the CAP Theorem, if you want to achieve Consistency and Partition Tolerance, you must give up Availability.

Or, to put it simply: if you detect a partition, you simply stop responding to requests! (More precisely, you reply with an error.) If you never respond with an answer, you can never respond with an outdated answer.

if network partition happens between two replica machines, isn't it impossible to achieve consistency?

Yes, it is. But, remember, the CAP Theorem says that in this case you lose Availability. So, you just respond with an error, and by not responding with an answer, you also don't respond with an outdated answer.

Remember, the definition of Consistency is (bold emphasis mine): every read receives the most recent write or an error.

So, the request erroring out satisfies the definition of Consistency.

How can we have both P and C in the second case?

By giving up A.

That is what the CAP Theorem is all about! You have to make a trade-off. If you want your system to be Available and Consistent, then you cannot tolerate network errors. However, since network errors are a fact of life, you have to tolerate them. But then it is impossible to always reply with the most recent write, because your nodes will get out of sync when the network fails. So, you can either always respond but risk responding with outdated data, or you can try to always respond with the latest data, but then you have to accept that you sometimes cannot respond at all.

It is trivially possible to achieve two out of three properties:

  • CA: Since we assume no partitions here, we can use a centralized datastore.
  • CP: Always respond with an error.
  • AP: Always respond with the initial value (ignoring all writes).

What the CAP Theorem proves is that it is impossible to achieve all three.

| improve this answer | |
  • How does a replica node know whether network partition happens or the other replica nodes are crashed? In the latter case, it shouldn't stop responding. – Tim Dec 28 '19 at 21:41
  • The CAP Theorem doesn't say anything about crashing, so crashing is irrelevant to the CAP Theorem. – Jörg W Mittag Dec 28 '19 at 22:15
  • That is not true. When a system has availability as "A" in CAP, it tolerates crashing of individual server processes. That belongs to the cases of either "A and P without C" or A and C without P" – Tim Dec 28 '19 at 22:16
  • 2
    Brewer and Gilbert / Lynch use slightly different definitions of "Availability", so if you don't say which of the two definitions you are talking about, this entire discussion is meaningless. For my answer, the difference doesn't matter, but I have the feeling that you are making an important distinction between the two, so it would really, really, really, really, really, really, really, really, really help if you wouldn't keep me guessing, but simply state which of the two you are talking about. – Jörg W Mittag Dec 28 '19 at 22:39
  • 1
    Which of the two papers? Gilbert / Lynch or Brewer? The definitions are subtly different. – Jörg W Mittag Dec 28 '19 at 22:43
1

How can we have both P and C in the second case?

I will answer with a common real-world example.

Common CP system in AWS cloud

Consider a distributed system made up of parts deployed to 3 datacenters (e.g. 3 AWS Availability Zones within a Region).

Now introduce a network partition (P) - e.g. the nodes in one datacenter is unreachable.

Use a consensus algorithm e.g. Raft to achieve consistency in the system (C). With Raft >50% of the nodes most be reachable, so with 2 of 3 datacenters reachable we are fine.

Voila - we have a CP system.

Critisism of CAP

While we are discussing CAP, it worth to mention recent critisism. CAP theorem is meant to be about trade-offs when designing a distributed system. But in a distributed system network partitions is never a trade-off - there is always chance for network partitions in any distributed system.

Source: A Critique of the CAP Theorem, Martin Kleppmann

Martin Kleppmann has written a highly recommended book about distributed systems: Designing Data-Intensive Applications.

As he suggests in his book, CAP Theorem is not something important anymore, there are other more well-definied properties about distributed systems that we should focus on instead.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.