[tlug]

Is it just me, or the proof appears to be incorrect? In the last example, the write operation should simply block before returning "done" to the client, before it's able to replicate the state to the other server. In fact, in a fault-tolerant system there cannot be just two servers, because it would be impossible to achieve a majority vote.

[DougBTX]

The example looks fine to me. If the writer blocks until the partition is resolved, then it isn’t Available for writes, so only meets CP.

[tlug]

OK, if you define the availability of writes in this way, that they must complete immediately, then indeed the availability part of CAP is not met.

However his definition reads: "every request received by a non-failing node in the system must result in a response"

It doesn't say anything about the timing of response. The network partition will be resolved eventually and thus the write operation will complete. Or it can time out and return an error, which is also fine based on the definition of availability (must result in a response).

[somenewacc]

Yes, but if you're allowed to timeout, then any system is trivially available, even a system where the nodes are always offline (simply timeout every request).

[j2kun]

I was under the impression that the partition need never be resolved.

[swagonomixxx]

Either the proof is incorrect or he/she set it up in a way to make it look extremely trivial.

The way I saw the proof go is: to satisfy CAP, you need replication, and you need high availability. To be consistent you need replication. But if you don’t have a reliable network, you don’t get reliable replication. Therefore you can’t be consistent. To me, this is a trivial result, and I’m not sure that this is what the CAP theorem intends to say?

It would be better to do, as you say, assume that a system is CA, And prove why it can’t be partition tolerant. Saying “network is unreliable” isn’t a suitable jump in argument IMO.

[j2kun]

It's trivial because (when you say things like "high availability", which is not precise nor does it apply to CAP) you're ignoring the precision required for a valid proof.

[fjsolwmv]

Trivial is subjective. The sketch of the proof is simple, but you skipped the details and it's not obvious to everyone at first.