5 ms·

What you describe is a CRDT, isn't it ?

ori_b 1y ago
No; there is no single consistent final state that the system must converge to if the parts go offline. If you have this document: a{uuid=1} and two clients send the following operations: b{uuid=2} insert-after{uuid=1} c{uuid=3} insert-after{uuid=1} then the following two documents are both valid final states: abc acb That's fine as long as you have an authoritative server that observes all events in a single order and a way to unwind misordered local state, but it means that it's not a CRDT.
- Yoric 1y ago
  If you have the additional semantics that says "operation with lowest uuid gets applied first", don't you essentially get a CRDT? I mean, a uuid is kind of a poor man's Lamport clock, isn't it?
  - ori_b 1y ago
    Yes, you can extend the algorithm that was described with additional semantics, and you can turn it into a CRDT.
- sdeframond 1y ago
  What about ordering concurrent operations by id? Then "abc" is the only consistent final state. I get what you mean though, having a central authority greatly relaxes the requirement.
  - 3cats-in-a-coat 1y ago
    We could generalize having a tree of known authorities upstream with what a CRDT does, resulting in both being two special cases of a more general consistent event processing model. CRDT makes the order of events commutative, hence the "authority" becomes a property of the math itself, rather than a physical service.
  - rendaw 1y ago
    How do you determine which operations are concurrent?
    - deleted 1y ago
      [deleted]
    - tangjurine 1y ago
      if there are multiple valid final states?
- YoumuChan 1y ago
  Like Raft is a "special case" of Paxos, this feels like a "special case" of CRDT. It has all the flavor of CRDT, but adds a leader and a different way for the total ordering (basically using leader's local lamport clock to break tie). Throw in leader reelection and some ledger syncing and then give everything some other names, I bet you can have "collaborative text editing on one page".
  - josephg 1y ago
    Yeah. It’s also quite inefficient by default - because you’re storing deleted items and you have a uuid per character. And you usually want the other parts from a crdt which this discards. Like, a consistent ordering rule for siblings. Doing so barely adds any code (like 10 lines or so) and it makes the system way more useful. I don’t really understand the benefit of doing this when text CRDTs are small, simple and fast.
  - nextaccountic 1y ago
    > Like Raft is a "special case" of Paxos Hey, can you elaborate? Googling this I can find this other HN comment https://news.ycombinator.com/item?id=32472189 https://news.ycombinator.com/item?id=32472189 that states the same thing, but nothing more
- motorest 1y ago
  > No; there is no single consistent final state that the system must converge to if the parts go offline. Sounds like a naive implementation of delta state CRDT. I mean, what if the author has this major epiphany that it's nice to sync states to get convergence?
- anon291 1y ago
  Yeah, so this is an operational transform where the transform operation is just identity.

No; there is no single consistent final state that the system must converge to if the parts go offline. If you have this document: a{uuid=1} and two clients send the following operations: b{uuid=2} insert-after{uuid=1} c{uuid=3} insert-after{uuid=1} then the following two documents are both valid final states: abc acb That's fine as long as you have an authoritative server that observes all events in a single order and a way to unwind misordered local state, but it means that it's not a CRDT.

Yoric 1y ago
If you have the additional semantics that says "operation with lowest uuid gets applied first", don't you essentially get a CRDT? I mean, a uuid is kind of a poor man's Lamport clock, isn't it?
- ori_b 1y ago
  Yes, you can extend the algorithm that was described with additional semantics, and you can turn it into a CRDT.
sdeframond 1y ago
What about ordering concurrent operations by id? Then "abc" is the only consistent final state. I get what you mean though, having a central authority greatly relaxes the requirement.
- 3cats-in-a-coat 1y ago
  We could generalize having a tree of known authorities upstream with what a CRDT does, resulting in both being two special cases of a more general consistent event processing model. CRDT makes the order of events commutative, hence the "authority" becomes a property of the math itself, rather than a physical service.
- rendaw 1y ago
  How do you determine which operations are concurrent?
  - deleted 1y ago
    [deleted]
  - tangjurine 1y ago
    if there are multiple valid final states?
YoumuChan 1y ago
Like Raft is a "special case" of Paxos, this feels like a "special case" of CRDT. It has all the flavor of CRDT, but adds a leader and a different way for the total ordering (basically using leader's local lamport clock to break tie). Throw in leader reelection and some ledger syncing and then give everything some other names, I bet you can have "collaborative text editing on one page".
- josephg 1y ago
  Yeah. It’s also quite inefficient by default - because you’re storing deleted items and you have a uuid per character. And you usually want the other parts from a crdt which this discards. Like, a consistent ordering rule for siblings. Doing so barely adds any code (like 10 lines or so) and it makes the system way more useful. I don’t really understand the benefit of doing this when text CRDTs are small, simple and fast.
- nextaccountic 1y ago
  > Like Raft is a "special case" of Paxos Hey, can you elaborate? Googling this I can find this other HN comment https://news.ycombinator.com/item?id=32472189 https://news.ycombinator.com/item?id=32472189 that states the same thing, but nothing more
motorest 1y ago
> No; there is no single consistent final state that the system must converge to if the parts go offline. Sounds like a naive implementation of delta state CRDT. I mean, what if the author has this major epiphany that it's nice to sync states to get convergence?
anon291 1y ago
Yeah, so this is an operational transform where the transform operation is just identity.