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.
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.
Readit News
It's usually better to pick the most interesting thing on the list and submit that instead.
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.
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
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.
> 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.
His writings are lucid and more readable than academic papers, IMO.
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