How does a distributed system both tolerate network partition and achieve consistency?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

I am going to add another perspective.

CAP: if partitioning is happening, then the system may be either available or consistent. The million dollar question is what is partitioning?

Let's say I have a raft/paxos based system with three nodes. For a new message to be accepted, the message has to be accepted by at least two nodes. In fact, the system tell the customer that the operation succeeded after two nodes are confirmed. The third node will be updated as well, but you need just two to confirm the operation.

Let's say your network became partitioned - two nodes are in partition A and the third node is in partition B.

From CAP point of view, your system as a whole is not partitioned! Since your system as a whole needs two nodes to be available and partition A has them - your system as a whole still available and consistent.

Bottom line - for whatever system you analyze, you have to define what partitioning means.