[HN Gopher] A highly-available move opertaion for replicated tre...
       ___________________________________________________________________
        
       A highly-available move opertaion for replicated trees [pdf]
        
       Author : a7b3fa
       Score  : 14 points
       Date   : 2022-03-26 11:54 UTC (1 days ago)
        
 (HTM) web link (martin.kleppmann.com)
 (TXT) w3m dump (martin.kleppmann.com)
        
       | narush wrote:
       | Super cool. Martin Kleppmann, the lead author on this paper, is
       | the author of Designing Data-Intensive Applications, which I
       | haven't read but have heard pretty awesome things about.
       | 
       | What I have done: watched his other talks about CRDTs (conflict-
       | free replicated data types). I'd recommend watching this video
       | [1] for an overview of what CRDTs are, why he cares about them,
       | and open problems (one of which he solves in this paper!).
       | 
       | A (potentially inaccurate) TLDR: local-first collaboration
       | software presents is a compelling alternative to the current way
       | collaboration is implemented in a client-server model.
       | Specifically: if we build tooling that makes it easy to build
       | collaborative experiences into your app without a server, then
       | we'll potentially be able to achieve the goals of
       | 'decentralization' (or, fuck the middleman or whatever you wanna
       | call it) in some real sense. Note that I'm not talking about
       | crypto coins here!
       | 
       | Very cool, very exciting!
       | 
       | [1] https://www.youtube.com/watch?v=Qytg0Ibet2E
        
         | narush wrote:
         | Ok, having read through the core of the algorithm, cool! Seems
         | like the main key here is that move operations have timestamps
         | associated with them, and this allows you to effectively
         | linearize the operations (and ignore ones that result in
         | invalid state).
         | 
         | The tradeoff: you need to store all the operations you've ever
         | seen, as you need to be able to detect conflicts between old
         | ones.
         | 
         | Question for the authors (if they are around): any ideas for
         | how we might get to efficient pruning of old operations?
         | 
         | My first thought was that you could have some notion of epoch,
         | and once you move beyond that epoch, you accept no new
         | operations from it. But then you realize that this requires
         | nodes to agree on moving between epochs, which seems like it
         | might require some fancy consensus protocol / a known set of
         | nodes / mad complexity.
         | 
         | I don't have any ideas. Do you all have some idea of how we
         | might be able to prune this old log? Or even sketches of ideas?
        
       ___________________________________________________________________
       (page generated 2022-03-27 23:01 UTC)