These are chat archives for RBMHTechnology/eventuate

6th
Oct 2016
Martin Krasser
@krasserm
Oct 06 2016 05:45

does it make sense to have additional internal fields for optimization purposes

there's nothing wrong doing so but it depends on the CRDT/application specifics, of course. What I cannot say ATM is whether your TreeCrdt approach is valid. Which specification have you follow? Did you take a look at section 3.4 Graphs in A comprehensive study of Convergent and Commutative Replicated Data Types? How do you preserve a tree shape under concurrent modification?

Alexander Semenov
@Tvaroh
Oct 06 2016 06:34
@krasserm I've found this https://arxiv.org/pdf/1201.1784.pdf - it's based on that paper. Trying to implement edge trees from section 2.6.
Alexander Semenov
@Tvaroh
Oct 06 2016 06:39
I've implemented two operations (createChildNode/deleteSubTree) for now, but didn't test it yet: https://gist.github.com/Tvaroh/f439101ea064f38f877853f16f13ade2
not sure regarding concurrent modification, in my understanding concurrent child node additions do not conflict (at least currently when I don't have children order)
Alexander Semenov
@Tvaroh
Oct 06 2016 06:44
and concurrent addition and deletion of same node seems impossible: a node should be already there to delete it, but cannot be added if already added... Not sure about all this though
Martin Krasser
@krasserm
Oct 06 2016 09:07
This message was deleted
Martin Krasser
@krasserm
Oct 06 2016 09:29

concurrent child node additions do not conflict

when you concurrently add the same node to different parents, you tree becomes a DAG.

and concurrent addition and deletion of same node seems impossible: a node should be already there to delete it, but cannot be added if already added... Not sure about all this though

you can add a node to a parent and that parent is concurrently deleted. In this case your tree becomes a forest. How is this resolved?

I didn't read the specification yet, I'm sure it is answered there, so I should read it before reviewing/commenting on your implementation. Thanks for sharing the paper! Looks very interesting and I'll try to read it as soon as I can.

Alexander Semenov
@Tvaroh
Oct 06 2016 09:42

Martin, exactly, those cases are described in the paper.

when you concurrently add the same node to different parents, you tree becomes a DAG

This case is described in section 2.3 and I didn't implement this yet.

you can add a node to a parent and that parent is concurrently deleted. In this case your tree becomes a forest. How is this resolved?

This case is described in section 2.2 and as I understand this should be handled when getting back CRDT value (value method in Eventuate API). Isolated islands can be ignored when re-constructing the tree from Set[Edge] and the underlying set CRDT can probably be "de-fragmented". In my current impl I just skip them because I start traversing from the root node and cannot reach them. Other options are recreate path, put under the root, and some others. But I'm currently targeting the "skip" one.

Martin Krasser
@krasserm
Oct 06 2016 10:03
I see, great you started working on it. Do you plan to make a contribution? Would love to see it in Eventuate.
Alexander Semenov
@Tvaroh
Oct 06 2016 10:11
it would be great, still don't know how far I can get currently, I've started reading these papers yesterday evening
and I'm far from understanding all the details
Martin Krasser
@krasserm
Oct 06 2016 10:13
no worries, I'm happy to help :smile:, just give me some time to catch up with the paper.
Alexander Semenov
@Tvaroh
Oct 06 2016 10:16
awesome!
Alexander Semenov
@Tvaroh
Oct 06 2016 15:06
Just realized that my TreeCrdt should probably wrap ORSetService instead of ORSet directly, otherwise it won't do anything. What if I want to have multiple underlying CRDTs (OR-sets for example), is it safe to use multiple ORSetServices from my CRDT?
Martin Krasser
@krasserm
Oct 06 2016 15:59

Just realized that my TreeCrdt should probably wrap ORSetService instead of ORSet directly

No, consider CRDTs as domain objects. They shouldn't depend on the service layer. Furthermore, CRDT services have an async API, how would you use it inside your custom CRDT? Take a look at ORCart as an example how to implement CRDTs on top of others.

Alexander Semenov
@Tvaroh
Oct 06 2016 16:00
Thanks, that's what I needed.