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.