3 ms·
Since it assumes all connected clients will receive all edits, why not just include a hash of the expected existing state of the text data before the offset and
by pmarreck 3y ago
Since it assumes all connected clients will receive all edits, why not just include a hash of the expected existing state of the text data before the offset and insertion/deletion/replacement instructions? That way, edits are more or less guaranteed to only be applied to appropriate states, and further changes can be accumulated in a dictionary with the hash key being the hash of the state of the data it’s expected to be applied to
Granted, that’s a lot of hash operations being redundantly computed from the same data, but it is trivial to understand and implement
- fastball 3y agoBecause asynchronous edits would never be applied with that system. If I make local edits to a document and you make remote edits to a document, the hash for your "expected state" will never match my document's state in the future because I have already made local changes. Yes, CRDTs require all clients receive all edits in order to guarantee convergence, but the updates not needing to be applied in a certain order (which is what you are proposing) is an important property for real-world distributed use-cases.
- steve76 3y ago[dead]
- jakelazaroff 3y agoThat’s only the case for CmRDTs, right? AFAIK CvRDTs (which send the whole state with every request) don’t impose any constraints on message order.
- fastball 3y agoAh, a bit of an "eats shoots and leaves" situations here. I mean: Yes, CRDTs require all clients receive all edits in order to guarantee convergence. They indeed do not need to be "in order", they merely need to receive all edits "to guarantee convergence". My insertion of "in order" was definitely confusing there.
- jakelazaroff 3y agoOops lol. I guess that applies to CvRDTs as well, since receiving a given state also means receiving all edits that caused it?