4 ms·

We are almost there, for lists and structs there are CDRT's but a move operation across the data structure is missing. Martin Kleppman (from automerge) talks ab

We are almost there, for lists and structs there are CDRT's but a move operation across the data structure is missing. Martin Kleppman (from automerge) talks about this in his talk "CRDTs: the hard parts"[0]. I also think a range move or range delete is missing from many of these algorithms. A submission here on HN did implement a range delete on rich text (but I forgot what the name was). [0]: https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw EDIT: Ah actually Peritext (which you linked to) was the article I was thinking of. I think the range delete would be useful for regular lists as well.

dmulligan 5y ago
See our latest paper [0] for an atomic move operation on replicated trees. [0]: https://dominicpm.github.io/publications/kleppmann-highly-available.pdf https://dominicpm.github.io/publications/kleppmann-highly-av...
- eternalban 5y ago
  Thank you for the paper. I have a peripheral question that’s been bugging me for a while and hopefully you can answer it: why aren’t the CS papers dated? If you hadn’t mentioned latest paper I would have to do footnote archeology to guess the general timeline.
  - dmulligan 5y ago
    Ha, I'm not sure! I just write papers, the vagaries of how and why journals and conference proceedings are published the way that they are is beyond my ken. Looking back through some of my other papers it seems that there's a mix --- some styles do include a date, especially those provided by the ACM, whilst others don't, including IEEE TPDS which is where the paper above is published. Who knows?
kazinator 5y ago
Syntax trees are lists and structs that have semantics. Conflict-free means that there is no conflict in the semantics, not just that the operations on a syntax tree shape result in a valid syntax tree shape. If we pass a syntax tree node with 12 children to two different servers which each add a node, we can easily resolve the structural conflict by adding both nodes, so now we have 14, and that may be a valid syntax tree. However, that 12-child node could be, say, a call to a function that takes 12 arguments. (So 11 are being passed, and one is defaulted). Adding one argument is semantically valid. Adding two means the call is bad.
- dnautics 5y ago
  > Conflict-free means that there is no conflict in the semantics, If you start with an incorrect premise you will wind up in a strange place. Conflict free has a specific meaning, and "semantics" can have multiple layers. If your threshold is perfect conflict free semantics at all levels, then you are indeed doomed. But a CRDT can provide a distributed, conflict-free canonical source substrate, with a specific semantic meaning at a minimally useful lowest semantic level. The challenge is to find transformations that are "good enough" to minimize conflicts at the higher semantic levels that you care about.
- monocasa 5y ago
  Practically, I don't think we're there yet. Yes, you can probably make a lisp-like that evals a currently existing crdt tree. The problem is, half the point (and the difficulty) of a crdt is constructing it so incomplete combinations of state updates kinda still make sense. I don't want a partial update causing the execution of gods knows what. And if we get real strictly transactional with the code tree updates, what's the point of the crdt in the first place? I'm not sure these issues can't be overcome, but it's admittedly still an open problem.
  - infogulch 5y ago
    > The problem is, half the point (and the difficulty) of a crdt is constructing it so incomplete combinations of state updates kinda still make sense. The real problem is that we're trying to solve this problem at the wrong level of abstraction. I think CRDTs can be reformulated as a subset of a larger replicated data type model that explicitly includes conflicts as part of the model, that any chosen set of transformations can be programmatically projected into a corresponding set of conflicts, that the choices of resolutions to those conflicts can be pre-packaged and composable, that some of those resolutions may need to be 'add a new transformation that choses between conflicts created by two other conflicting transformations' (basically exposing the problem up into the model of the data type), and that a composition of chosen resolutions can be proved to be fully conflict-free. The biggest benefits of this approach are: 1. It enables modeling domains where conflicts are an unavoidable part of the domain itself. 2. It allows tuning an initially pessimistic model where all conflicts are exposed to the user by gradually adjusting the conflict resolution choices so that it becomes more conflict-free over time; especially by composing known conflict-free subsets of the model into larger conflict-free subsets.
josephg 5y ago
Martin Kleppman has proposed using range deletes for all deletes in automerge[1]. In diamond types (my own CRDT) I'm still on the fence about whether or not this is a good idea. The downside is if you select & delete two functions, and I concurrently insert a new function in the middle of that range, then the merged result will delete my function. Thats a really bad outcome - but its pretty rare in practice. A much more common case is, I deleted 2 lines of code and you modify a parameter in one of those function calls. In this case, using range deletes your edits will also be deleted (which is what we want). Using individual deletes, the result will end up with some random junk left behind, in the form of whichever characters I typed. When we're editing code as plain text, I don't think there's any such thing as perfect here. For asyncronous collaborative editing (like git), I think generating conflict markers & human supervision for merging might be the best answer. I'd love to see someone make a prototype editor which can do AST-level concurrent editing. That would be super interesting in a bunch of ways - like, you could use the AST to do syntax highlighting in any editor too. But I'm not sure how it'd merge code when the parse tree is invalid - like, if I remove a closing brace (}) early in the function, what happens? There's a lot of cool ideas in this space. I'm excited to see people explore them as CRDTs get more popular and more mature. [1] https://github.com/automerge/automerge/issues/401 https://github.com/automerge/automerge/issues/401
- lewisjoe 5y ago
  Makes sense. Ranged deletes might be key to handle rich-text table mutations. Seph, thanks for showing up. Author here. This write-up is just a generalization I've landed on, while thinking about the nature of another problem: handling block elements in rich text in Peritext - a project you've collaborated with I guess. Here's the link - https://github.com/inkandswitch/peritext/issues/27 https://github.com/inkandswitch/peritext/issues/27 Do throw your thoughts too. I'd be happy pick your brain on this :)
  - josephg 5y ago
    Commented in the github thread :)
- thomasikzelf 5y ago

dmulligan 5y ago

See our latest paper [0] for an atomic move operation on replicated trees. [0]: https://dominicpm.github.io/publications/kleppmann-highly-available.pdf https://dominicpm.github.io/publications/kleppmann-highly-av...

eternalban 5y ago
Thank you for the paper. I have a peripheral question that’s been bugging me for a while and hopefully you can answer it: why aren’t the CS papers dated? If you hadn’t mentioned latest paper I would have to do footnote archeology to guess the general timeline.
- dmulligan 5y ago
  Ha, I'm not sure! I just write papers, the vagaries of how and why journals and conference proceedings are published the way that they are is beyond my ken. Looking back through some of my other papers it seems that there's a mix --- some styles do include a date, especially those provided by the ACM, whilst others don't, including IEEE TPDS which is where the paper above is published. Who knows?

kazinator 5y ago

Syntax trees are lists and structs that have semantics. Conflict-free means that there is no conflict in the semantics, not just that the operations on a syntax tree shape result in a valid syntax tree shape. If we pass a syntax tree node with 12 children to two different servers which each add a node, we can easily resolve the structural conflict by adding both nodes, so now we have 14, and that may be a valid syntax tree. However, that 12-child node could be, say, a call to a function that takes 12 arguments. (So 11 are being passed, and one is defaulted). Adding one argument is semantically valid. Adding two means the call is bad.

dnautics 5y ago
> Conflict-free means that there is no conflict in the semantics, If you start with an incorrect premise you will wind up in a strange place. Conflict free has a specific meaning, and "semantics" can have multiple layers. If your threshold is perfect conflict free semantics at all levels, then you are indeed doomed. But a CRDT can provide a distributed, conflict-free canonical source substrate, with a specific semantic meaning at a minimally useful lowest semantic level. The challenge is to find transformations that are "good enough" to minimize conflicts at the higher semantic levels that you care about.
monocasa 5y ago
Practically, I don't think we're there yet. Yes, you can probably make a lisp-like that evals a currently existing crdt tree. The problem is, half the point (and the difficulty) of a crdt is constructing it so incomplete combinations of state updates kinda still make sense. I don't want a partial update causing the execution of gods knows what. And if we get real strictly transactional with the code tree updates, what's the point of the crdt in the first place? I'm not sure these issues can't be overcome, but it's admittedly still an open problem.
- infogulch 5y ago
  > The problem is, half the point (and the difficulty) of a crdt is constructing it so incomplete combinations of state updates kinda still make sense. The real problem is that we're trying to solve this problem at the wrong level of abstraction. I think CRDTs can be reformulated as a subset of a larger replicated data type model that explicitly includes conflicts as part of the model, that any chosen set of transformations can be programmatically projected into a corresponding set of conflicts, that the choices of resolutions to those conflicts can be pre-packaged and composable, that some of those resolutions may need to be 'add a new transformation that choses between conflicts created by two other conflicting transformations' (basically exposing the problem up into the model of the data type), and that a composition of chosen resolutions can be proved to be fully conflict-free. The biggest benefits of this approach are: 1. It enables modeling domains where conflicts are an unavoidable part of the domain itself. 2. It allows tuning an initially pessimistic model where all conflicts are exposed to the user by gradually adjusting the conflict resolution choices so that it becomes more conflict-free over time; especially by composing known conflict-free subsets of the model into larger conflict-free subsets.

josephg 5y ago

Martin Kleppman has proposed using range deletes for all deletes in automerge[1]. In diamond types (my own CRDT) I'm still on the fence about whether or not this is a good idea. The downside is if you select & delete two functions, and I concurrently insert a new function in the middle of that range, then the merged result will delete my function. Thats a really bad outcome - but its pretty rare in practice. A much more common case is, I deleted 2 lines of code and you modify a parameter in one of those function calls. In this case, using range deletes your edits will also be deleted (which is what we want). Using individual deletes, the result will end up with some random junk left behind, in the form of whichever characters I typed. When we're editing code as plain text, I don't think there's any such thing as perfect here. For asyncronous collaborative editing (like git), I think generating conflict markers & human supervision for merging might be the best answer. I'd love to see someone make a prototype editor which can do AST-level concurrent editing. That would be super interesting in a bunch of ways - like, you could use the AST to do syntax highlighting in any editor too. But I'm not sure how it'd merge code when the parse tree is invalid - like, if I remove a closing brace (}) early in the function, what happens? There's a lot of cool ideas in this space. I'm excited to see people explore them as CRDTs get more popular and more mature. [1] https://github.com/automerge/automerge/issues/401 https://github.com/automerge/automerge/issues/401

lewisjoe 5y ago
Makes sense. Ranged deletes might be key to handle rich-text table mutations. Seph, thanks for showing up. Author here. This write-up is just a generalization I've landed on, while thinking about the nature of another problem: handling block elements in rich text in Peritext - a project you've collaborated with I guess. Here's the link - https://github.com/inkandswitch/peritext/issues/27 https://github.com/inkandswitch/peritext/issues/27 Do throw your thoughts too. I'd be happy pick your brain on this :)
- josephg 5y ago
  Commented in the github thread :)
thomasikzelf 5y ago