Hacker News Reader

Comment by sdeframond | Hacker News Reader

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

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.

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?

Yes, you can extend the algorithm that was described with additional semantics, and you can turn it into a CRDT.

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.

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.

How do you determine which operations are concurrent?

if there are multiple valid final states?

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".

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.

> 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 that states the same thing, but nothing more

> 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?

Yeah, so this is an operational transform where the transform operation is just identity.

Reply on news.ycombinator.com