CRDT Papers | Hacker News Reader

CRDT Papers

crdt.tech

58 pointsluu11 comments

Lists usually don't make great HN submissions: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor..., as HN itself is already a list.

It's usually better to pick the most interesting thing on the list and submit that instead.

I've made an attempt to create a unifying theory around conflict free replicated data types: https://www.alexahn.com/2022/05/conflict-free-replicated-pro...

The gist is that all data types can be represented as programs, which have grammars, and ultimately can be converted to ASTs. The interpretation of the program is what leads to a value. I merge the ideas of state-based and operation-based CRDTs into one by enforcing an associative property, which is only possible if operations and states can both be built incrementally.

As an example, suppose we are applying a set of operations to a state: state_0; state_1 = op(state_0, arg_0); state_2 = op(state_1, arg_1) which can be represented as: op(op(state_0, arg_0), arg_1) We can think of this as collapsing on the state side, in the sense that changes are encoded in the state. We can also collapse on the operation side, in the sense that changes are encoded in the operation: op_0 = op(arg_0); op_1 = op(op_0, arg_1) which can be represented as: op(state_0, op(op(arg_0), arg_1)) I believe a CRDT that can collapse on either end will allow you to build conflict free replicated programs. Fundamentally what you are looking for is op(op(state, arg_0), arg_1) = op(state, op(arg_0, arg_1)), which is associativity.

Is trying to be the “essential CRDT”? CRDT didn’t spring from the quivering Internet jello fully formed in 2006. I feel this should go further back. I recall doing CRDT-like things for distributed message threading in ’97, and I’m pretty sure it wasn’t original work. E.g. I recall some reading some paper[1] at the time which referenced Lamport’s 1978 note on distributed time[2].

The Awesome CRDT[3] references earlier material too.

[1] https://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algo... [2] https://www.ics.uci.edu/~cs230/reading/time.pdf [3] https://github.com/alangibson/awesome-crdt

This is a list of research papers on CRDTs, published on the main open source reference site about CRDTs, curated by Martin Kleppmann, Annette Bieniusa and Marc Shapiro.

That’s about as canonical as you can get.

The papers obviously reference the prior work.

What’s interesting to me is to see how much new work continues to build on CRDTs and push the boundaries of what’s possible for AP, causal and mixed consistency systems.

For context, I suspect this has been posted after Martin Kleppmanna (one of the creators of CRDTs) post today:

> There are now over 150 published papers about CRDTs (let me know if any are missing). Feels like it’s becoming a real field of research!

https://nondeterministic.computer/@martin/110180829603015471

It's not just a real field of research, it's a real tool used significantly in industry.

Evan Wallace (former CTO of Figma) made an interesting CRDT post in November: https://www.madebyevan.com/algos/crdt-tree-based-indexing/

His writings are lucid and more readable than academic papers, IMO.

Octobase is a new CRDT back-end data synchronizer written in Rust that I am evaluating for a project.

It seems quite practical for multi-player document editing and collaboration.

Currently AGPLv3 licensed but is apparently changing to MPLv2 once fully stable, as per the License section on the GitHub readme

https://github.com/toeverything/OctoBase

What is a CRDT?

Conflict-free Replicated Data Types

Thank You!

404?

Reply on news.ycombinator.com