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

A difference seems to be that there still is a leader in this protocol whereas in epaxos there is not a (stable) leader.

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.

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.

Nice to have the TLA+ spec in the repo. Though it doesn't have the details on leader election.

https://github.com/xline-kv/Xline/blob/master/curp/tla%2B/cu...

For those interested in this sort of thing, see also Raft's TLA+ specification: https://github.com/ongardie/raft.tla

The CURP paper doesn't define a new leader election algorithm and presumes you use an existing one like raft¹. Xline is using raft based on the readme

https://github.com/xline-kv/Xline/tree/master/curp/tla%2B

¹warning, I skimmed and ctrl-fd for "leader election"

Or you could just use a CRDT.

You don't need PAXOS, RAFT, or CURP to implement a key-value store. Those are distributed state machines, all you need is distributed state.

That means you don't need a leader election. You don't need a leader. You don't need any round trips. You don't need coordination.

PAXOS was the only game in town for many decades, but there are better ways to do this now.

CRDTs don’t magically solve the ordering problem, though they do solve a bunch of other problems around merge conflicts.

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.

What are the rare cases where its generally the right choice? Just curious

This is really worthy of a good blog post or article, if it hasn't been written yet.

Yes, it is. I'm trying to spread the word... but maybe this is the kind of thing that needs a good full-size articulation for it to really click.

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.

This isn't my area, so I don't really know.

But, if CRTDs allow independent operation, don't they check the high availability box?

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.

See also the Jepsen page on consistency levels.

https://jepsen.io/consistency/models/strict-serializable

In this article, CURP stand for "Consistent Unordered Replication Protocol," not "Controlled Unclassified Information (CUI) Repository Protocol" as many would assume.

And KV stands for Key Value.