So this seems to be talking about consensus algorithms that have a fast path when a new transaction doesn’t conflict with in flight transactions and a slow path when there is a conflict. I think this idea is very nicely explored/articulated in the egalitarian paxos paper. Though perhaps there’s additional nuance im missing related to the semantics of the transactions in a kv store context
It looks like the improvement of their protocol is that the client talks to all nodes immediately, rather than talking to the leader who then talks to the rest of the cluster. Depending on the location of the client relative to the rest of the cluster, that can be faster.
CRDTs are eventually consistent whereas Raft/Paxos consensus enables strict consistency with high availability. If you don't need strict consistency or you don't need high availability, then yeah, you don't need consensus.
You can't really have "independent operations" on a bank account.
If node A sees deposit,withdraw and node B sees withdraw,deposit one of those is business-as-usual, the other is overdraft. You can't have a "high availability" system where some parts of the system are acting like it's okay, and other parts aren't.
Not everything is a bank, but a lot of things are often more-like-a-bank than they first appear...
Many things provide high availability, including hot backups that you manually promote to leader (i.e. the traditional database setup).
However, it's distributed consensus that solves for strict serializability (I should say, not strict consistency) and high availability as a combination.
They completely solve the ordering problem of a key-value store as described in this article.
What they don't do is give you a global linear ordering. But you don't need that in a key-value store, and you don't need that in most distributed computing.
People keep reaching for PAXOS and RAFT when they don't need it. It's pretty rare that you need a distributed linearization.
So, I don't think that this optimization is new (fast path for commutative operations), but it's very difficult to get correct AFAICT, because in order to garner full optimizations, you must know about the invariants being preserved. For example, adds can always be non-conflicting for a bank account, if say, the invariant is that a bank account balance must never go below 0, but withdrawals need global consensus.
The earliest knowledge I have of this is Generalized Paxos, but I believe there's more recent work with the likes of Egalatarian Paxos. I think there were even some CRDTs that mixed strong consistency and weak consistency.
In this article, CURP stand for "Consistent Unordered Replication Protocol," not "Controlled Unclassified Information (CUI) Repository Protocol" as many would assume.
