1. 13

I’m seeing CRDTs back in headlines on my favorite places to hang out in the internet. I wrote this particular post back in 2012, and it provides a quick explanation of how CRDTs work. Despite the age, I find the post stands up to the test of time if you take out all the references to Riak.

  1.  

  2. 2

    I have been struggling to conceptualize a use of CRDTs for a particular use-case, and it seems like I found that it is not possible to do…

    I have product catalog that’s represented as a tree, that I would like to make ‘globally’ available for modifications. Each node in the product catalog tree is ( item-id, description, catalog-membership-fields, parent-item-id). An item could be added or removed along anywhere in a tree path, concurrently (eg one client is doing add on node-A, the other is doing a remove of its parent on node-B)

    Just recently I found Paul Frazee’s notes [1]

    In general, maintaining a particular shape, such as a tree or a DAG, cannot be done by a CRDT. Such a global invariant cannot be determined locally; maintaining it requires synchronization….. … They include an illustration which shows that a remove could conflict with a concurrent add. The invariant that “removal does not disrupt paths between distinct vertices” would have to be enforced globally.

    Not sure if there is a ‘registry’ of use cases enumerating data structures + operations invariants that do not fit CRDTs, but it might be useful for folks such as myself, who are new to this.

    [1] https://github.com/pfrazee/crdt_notes

    1. 5

      This recent video talks about how they solved that exact problem - https://lobste.rs/s/ota80z/crdts_hard_parts

      1. 1

        thank you! will take a look