Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

CRDT: Implement ORSet, for Receptionist #26

Closed
ktoso opened this issue Aug 22, 2019 · 0 comments · Fixed by #41
Closed

CRDT: Implement ORSet, for Receptionist #26

ktoso opened this issue Aug 22, 2019 · 0 comments · Fixed by #41
Assignees
Milestone

Comments

@ktoso
Copy link
Member

ktoso commented Aug 22, 2019

Implement an Observed Removed Set datatype.

For each element in the set, a list of add-tags and a list of remove-tags are maintained. An element is inserted into the OR-Set by having a new unique tag generated and added to the add-tag list for the element. Elements are removed from the OR-Set by having all the tags in the element's add-tag list added to the element's remove-tag (tombstone) list. To merge two OR-Sets, for each element, let its add-tag list be the union of the two add-tag lists, and likewise for the two remove-tag lists. An element is a member of the set if and only if the add-tag list less the remove-tag list is nonempty.[2] An optimization that eliminates the need for maintaining a tombstone set is possible; this avoids the potentially unbounded growth of the tombstone set. The optimization is achieved by maintaining a vector of timestamps for each replica.[15]

@ktoso ktoso added 3 - in progress Ticket is being worked on t:crdt labels Aug 23, 2019
@ktoso ktoso added this to the 0.1.0 milestone Aug 23, 2019
@ktoso ktoso closed this as completed in #41 Aug 27, 2019
ktoso pushed a commit that referenced this issue Aug 27, 2019
* CRDT: Implement ORSet

Motivation:
Receptionist needs ORSet.

Changes:
Implement an optimized ORSet based on [An optimized conflict-free replicated set](https://hal.inria.fr/file/index/docid/738680/filename/RR-8083.pdf).

Influenced by Bartosz Sypytkowski's CRDT [articles](https://bartoszsypytkowski.com/optimizing-state-based-crdts-part-2/) and [implementation](https://github.com/Horusiath/crdt-examples), as well as [Akka's `ORSet`](https://github.com/akka/akka/blob/master/akka-distributed-data/src/main/scala/akka/cluster/ddata/ORSet.scala).

Result:
This resolves #26.
@ktoso ktoso removed the 3 - in progress Ticket is being worked on label Aug 27, 2019
ktoso pushed a commit that referenced this issue Aug 31, 2019
* CRDT: Implement ORSet

Motivation:
Receptionist needs ORSet.

Changes:
Implement an optimized ORSet based on [An optimized conflict-free replicated set](https://hal.inria.fr/file/index/docid/738680/filename/RR-8083.pdf).

Influenced by Bartosz Sypytkowski's CRDT [articles](https://bartoszsypytkowski.com/optimizing-state-based-crdts-part-2/) and [implementation](https://github.com/Horusiath/crdt-examples), as well as [Akka's `ORSet`](https://github.com/akka/akka/blob/master/akka-distributed-data/src/main/scala/akka/cluster/ddata/ORSet.scala).

Result:
This resolves #26.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants