I view this as a generalization of optimistic locking on source control. I don't envy my past self for having to checkout code with a lock that I was going to change it.
t0: alice "I lost my wedding ring." t1: alice "Nevermind, I found it."
Because of the peculiar circumstances around traffic at this moment, the nodes closest to Alice don't get that second message. Instead, the nodes closest to bob receive the message, and bob sees the message before alice does. Bob replies, and because everything is okay with the nodes close to him, the message gets passed back to alice. What happens? The node alice is reading from is having issues, so things are re-routed to bob's cluster. Bob's message has a timestamp that legitimately puts it in between the two messages from alice because the server clocks are off a little.
Now, whatever was going wrong with the cluster close to alice has repaired and it receives bob's message with a node in the graph that alice's cluster is completely unaware of because it hasn't caught up.
Bob's message is telling the cluster, "You can't display this message (c) unless you have already acknowledged prior messages (a and b)." Alice's cluster says, "I have message a, but b doesn't exist."
According to the paper, bob's message will never be delivered to alice until the cluster closest to alice sync's up with some other remote cluster and her second message is restored. Which, of course, we know can fail to happen with Cassandra, and the projects mentioned are forks of Cassandra.
I can't prove it formally, but this feels like the problems you run into with messaging queues: you can guarantee at least once delivery or at most once delivery, but not both at the same time. But a different set of tradeoffs: under this theoretical model, you can deliver in order or not at all.
Obviously, this is a use case facebook would care about. But I don't know that it's generally applicable for very many use cases.
Unless I'm missing something important, transmitting the graph doesn't really do anything to change the fact that this is eventual consistency and brings all of the problems that come with that. I guess the difference between this and eventual consistency and causal consistency is that one provides out-of-date/out-of-order data in an error condition, and the other presumably provides nothing but an error. YMMV.
But to a larger point, calling a combined system of client libraries with a forked version of Cassandra some other-category-of-consistency datastore seems to me to be disingenuous. You're no longer talking about a data store. You're talking about an ecosystem of libraries and developer practices and a datastore that work together to provide some workarounds for the challenge that CAP theorem presents. This is, unless I'm badly misreading the article, granting a lot of leeway.
I also find it unfortunate that the optimized version of this only compared throughput without discussing failure cases at all. CAP theorem is all and only about what can be guaranteed in failure cases. We need to agree from now on that if we're going to talk about CAP theorem, that we are talking about guarantees in failure modes, not optimistic modes. Otherwise, there is no value found by invoking the theorem.
And this strikes me as a particularly bold assumption given almost anyone's real-world experience: "It is partition-tolerant because all reads are in the local data center (partitions are assumed to occur only in the wide area, not in the local data center)."
No, kind sir. It is not partition tolerant if that is your assumption. It has already failed the P part of CAP if that's an assumption you are relying on.
I'm not trying to shoot the article or the authors down here. Now that CAP theorem has been proved to be a conceptual "pick 2" situation, of course we have to do everything we can to make up for that and do our best, and this seems like a great effort at that.
But I think that the authors fundamentally misunderstand the point of writing a paper about a data store and its relationship to CAP theorem. It's not about optimistic cases, software development patterns, or libraries that sit on top of the data store.
It's about guarantees of what happens in failure modes. From reading this paper, all I can tell with certainty is that it's not consistent, and it's not partition-tolerant. It's highly available. To me that seems like it's a step backwards from platforms that are, or at least aim to be, CA or AP.
EDIT:
I did look at the actual paper [0], they provide a strong consistency within local data center, and a causal consistency with convergent conflict handling across data centers. They presume that each client resides within a data center, so it is essentially a variant of fixed entry point solution I mentioned earlier.
Additionally, what it quite important, you lose causal consistency if client connects to different data centers.
[0] Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS
