3 ms·
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
by tlug 8y ago
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 8y agoThe 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 8y agoOK, 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 8y agoYes, 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 8y agoI was under the impression that the partition need never be resolved.
- swagonomixxx 8y agoEither 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.
- fjsolwmv 8y agoTrivial is subjective. The sketch of the proof is simple, but you skipped the details and it's not obvious to everyone at first.
- j2kun 8y agoIt'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.