[HN Gopher] CRDT Papers
       ___________________________________________________________________
        
       CRDT Papers
        
       Author : luu
       Score  : 41 points
       Date   : 2023-04-11 19:21 UTC (3 hours ago)
        
 (HTM) web link (crdt.tech)
 (TXT) w3m dump (crdt.tech)
        
       | prideout wrote:
       | 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.
        
       | dang wrote:
       | 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.
        
       | no-s wrote:
       | 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
        
         | thruflo wrote:
         | 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.
        
       | samwillis wrote:
       | 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.
        
       | alexahn wrote:
       | 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.
        
       | mmerlin wrote:
       | 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
        
       | RecycledEle wrote:
       | What is a CRDT?
        
       | alixanderwang wrote:
       | 404?
        
       ___________________________________________________________________
       (page generated 2023-04-11 23:02 UTC)