3 ms·

As long as all clients agree on the order of CRDT operations then cycles are no problem. It's just an invalid transaction that can be dropped. Invalid or contra

by jdvh 2y ago

As long as all clients agree on the order of CRDT operations then cycles are no problem. It's just an invalid transaction that can be dropped. Invalid or contradictory updates can always happen (regardless of sync mechanism) and the resolution is a UX issue. In some cases you might want to inform the user, in other cases the user can choose how to resolve the conflict, in other cases quiet failure is fine.

jakelazaroff 2y ago
Unfortunately, a hard constraint of (state-based) CRDTs is that merging causally concurrent changes must be commutative. ie it is possible that clients will not be able to agree on the order of CRDT operations, and they must be able to arrive at the same state after applying them in any order.
- jdvh 2y ago
  I don't think that's required, unless you definitionally believe otherwise. When clients disagree about the the order of events and a conflict results then clients can be required to roll back (apply the inverse of each change) to the last point in time where all clients were in agreement about the world state. Then, all clients re-apply all changes in the new now-agreed-upon order. Now all changes have been applied and there is agreement about the world state and the process starts anew. This way multiple clients can work offline for extended periods of time and then reconcile with other clients.
  - dboreham 2y ago
    That's not how the CRDT concept works.
    - jdvh 2y ago
      You're free to argue that this isn't "pure" CRDT, but the CRDT algorithm still runs normally, just a bit later than it otherwise would.
  - satvikpendem 2y ago
    Eg-walker seems similar to what you're proposing [0]. A more in-depth video by the creator [1]. [0] https://loro.dev/docs/advanced/event_graph_walker https://loro.dev/docs/advanced/event_graph_walker [1] https://www.youtube.com/watch?v=rjbEG7COj7o https://www.youtube.com/watch?v=rjbEG7COj7o

by jdvh 2y ago

jakelazaroff 2y ago

Unfortunately, a hard constraint of (state-based) CRDTs is that merging causally concurrent changes must be commutative. ie it is possible that clients will not be able to agree on the order of CRDT operations, and they must be able to arrive at the same state after applying them in any order.

jdvh 2y ago
I don't think that's required, unless you definitionally believe otherwise. When clients disagree about the the order of events and a conflict results then clients can be required to roll back (apply the inverse of each change) to the last point in time where all clients were in agreement about the world state. Then, all clients re-apply all changes in the new now-agreed-upon order. Now all changes have been applied and there is agreement about the world state and the process starts anew. This way multiple clients can work offline for extended periods of time and then reconcile with other clients.
- dboreham 2y ago
  That's not how the CRDT concept works.
  - jdvh 2y ago
    You're free to argue that this isn't "pure" CRDT, but the CRDT algorithm still runs normally, just a bit later than it otherwise would.
- satvikpendem 2y ago
  Eg-walker seems similar to what you're proposing [0]. A more in-depth video by the creator [1]. [0] https://loro.dev/docs/advanced/event_graph_walker https://loro.dev/docs/advanced/event_graph_walker [1] https://www.youtube.com/watch?v=rjbEG7COj7o https://www.youtube.com/watch?v=rjbEG7COj7o