CRDT semantics

[pgte]

I've been looking to Gun and I think it's awesome. I'm trying to evaluate if this can be used for lossless collaborations, so I guess my question is:

Using Gun, could you create a CRDT that is lossless and efficient?
I'm thinking of an example for concurrent text editing (like an RGA, as defined on page 34 of this paper).
Could you provide an example / guidelines of how to create this?

[pgte]

Just for reference, here is the abstract implementation of such a delta-CRDT:
https://github.com/ipfs-shipyard/js-delta-crdts/blob/master/src/rga.js

[Dletta]

@pgte I remember seeing a tech talk from the creator of GUN @amark and I believe the CRDT can be anything you want as long as it accepts the API calls. At least most part of the code is modular and can be 'hooked' into to allow other algorithms to take over some of the functions of the code. The current Conflict Resolution Algorithm is called HAM

[pgte]

@Dletta I've read through the documents but it's still not clear to me how to achieve this..

[Dletta]

This is the current HAM code, for prototyping you might be able to just fork gun.js and propose a change, @amark might need to answer if there is a better way to infuse your own CRDT.

gun/gun.js

Line 208 in 5b62437

;USE(function(module){

[amark]

@pgte yes, you can create any other CRDT as a data structure on top of GUN's base CRDT.

In the case of collaborative text editing, I did a demo of building this on top of GUN several years ago:

https://youtu.be/rci89p0o2wQ

And we even did a whole cartoon explainer (sorry, I'm not much for academic papers) on generic algorithms for this type of stuff:

https://gun.eco/explainers/school/class.html

I haven't seen anybody implement RGA specifically on top of GUN, but given how short the code you sent over, it should be pretty easy. (Although the "delete" would need to be a null tombstone, but that is fine)

Like I sent before, it is probably easiest to start by looking at the counter CRDT for "how to start saving data to GUN with a custom extension"

https://gun.eco/docs/Counter

You note that it is very basic, RGA would be similar, you'd probably have some GUN extension (just a JS method/function, that makes it easier for developers to use) like

Gun.chain.rga = function(...

Then internally, like with counter, you'd call gun.put( or gun.set( or whatever other commands to save data to the graph (put and set are themselves just extensions like RGA is, nothing fancy here) where you'd build/construct a graph/tree/table, or you could be lazy and just do something like:

// fictional code
var myData = {
  rgaTree: {left: {}, right: {}}
}
myData.rgaTree.left.next = myData.rgaTree.right;
myData.rgaTree.right.prev = myData.rgaTree.left;
// yes! circular references are supported!
gun.put(myData);

Obviously you might want to be more detailed and control the UUIDs with the cuids and stuff, but you get the point.

@Dletta thanks! In this case, nobody would actually replace HAM or "inject" a CRDT along side it, just @pgte would model the CRDT's data structure on GUN (probably with a nice easy API via a GUN extension), then you'd also have that extension support a callback, which if passed... you'd gun.get(... through the RGA graph/tree and run the various RGA logic before spitting the result back out to the developer. This tree can be dynamically mutated concurrently inside of GUN by many peers!

Then, GUN will save that dynamically changing and updating data to disk via one of (many) storage engines, such as IPFS! So IPFS can host the persistence of data over time, and GUN can manage the O(1) tree lookups that are the mutable/changing/dynamic tree/graph structures.

[amark]

@pgte closing, as this is not a bug, please feel free to ask further questions on http://stackoverflow.com/questions/tagged/gun or for help on https://gitter.im/amark/gun ! :)

[pgte]

Following up here: https://stackoverflow.com/questions/52094556/how-can-i-implement-a-lossless-crdt-using-gun