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

Implement CRDT Move Convergence Mechanism #987

Open
hackerwins opened this issue Aug 29, 2024 · 0 comments
Open

Implement CRDT Move Convergence Mechanism #987

hackerwins opened this issue Aug 29, 2024 · 0 comments
Labels
enhancement 🌟 New feature or request hard 🧑‍🔬 Difficult to deal with or require research

Comments

@hackerwins
Copy link
Member

hackerwins commented Aug 29, 2024

Description:

Currently, Move operations differ from Insert or Delete operations in that they struggle to establish a commutative property solely through operations. The following failure cases exemplify the issue:

  1. In Array, when multiple Move operations are executed simultaneously, if the reference node (Previous) moves its value, the Array's structure is maintained, but the values diverge: here.

  2. In Tree, if concurrent Move operations occur and an Ancestor nodes move its value, the Tree's structure is compromised: here.

To resolve these issues, the current approach by OPSet(Specifying a Tree with Atomic Moves, Automerge) and REG(Movable Tree, Loro) involves sorting the operations before re-execution to achieve convergence.

The convergence mechanism consists of two main components:

A. To re-execute operations across all replicas to determine the final state.
B. Allow for the cancellation of certain operations based on specific rules(e.g., cycle in Tree) during re-execution.

Unlike the two systems(OPSet, REG), Yorkie system has all operations in the central server, but the replica only has the state, so we need to think about how to introduce it.

Why:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement 🌟 New feature or request hard 🧑‍🔬 Difficult to deal with or require research
Projects
Status: Backlog
Development

No branches or pull requests

1 participant