Introduction to CURP Protocol (opens in new tab)

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

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.

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...

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.