Chronofold: A data structure for versioned text (2020)

https://arxiv.org/abs/2002.09511

by tempodox • 5 years ago

207 23 5 years ago

Would appreciate anyone knowledgeable in the field who could provide a "layman's" breakdown of the relative merits of this approach vs OT and CRDTs. I'm afraid it's a bit above my head.

jitl3• 5 years ago

This is a CRDT.

I think the first page or so of the paper is very approachable, explaining well the history of these kinds of ideas and the advantages of Chronofold, did you try reading it?

claytongulick2• 5 years ago

I read the abstract and was a bit lost, I guess.

I took from it that this was a novel "locality" approach that was different than CRDT'S.

This is far from my area of expertise, so I guess 'approachable' is relative? Was hoping that (in the fine tradition of HN) someone who knows a lot more about this stuff could chime in.

I'd really like to learn some of this for a number of projects I'm working on, and I'm not sure where the best place to direct my focus is. ShareJS is OT based, iirc, and but quill js has some basic support for it too. CRDTs are a bit voodoo to me. This is something else?

Sorry if it's a remedial question, would appreciate any advice or insight.

vicda• 5 years ago

You say that like they have heard of the acronym CRDT before.

Don't let the curse of knowledge be an excuse to be rude to people.

AnthonBerg• 5 years ago

I like this one out of a series of similar papers: https://arxiv.org/abs/1905.01518

Maybe not light reading?, but accessible still.

josh11b• 5 years ago

I suspect this is a follow-up to this recent article: https://news.ycombinator.com/item?id=28017204

jitl3• 5 years ago

I submitted it right after reading the paper from gritzko’s post but the story didn’t get any traction :( https://news.ycombinator.com/item?id=28020792

mikewarot• 5 years ago

So, this is essentially cache invalidation, mixed with relativity/causality... the hardest aspects of two different fields, all rolled into one data structure/algorithm.

I found it interesting, and something I will have to read a few more times before all the details make sense.

The idea of collapsing the structure when individual changes are no longer needed is appealing in terms of space saving.

I look forward to seeing this implemented.

DougBTX• 5 years ago

this is essentially cache invalidation, mixed with relativity/causality

In a sense these are quite closely related, the challenge with caches is when they go out of sync with their source data, as then reads/writes against the cache/source could appear to violate causality.

wokwokwok• 5 years ago

This is from April 2020.

You can find a few implementations (1, 2) to play with now if you’re interested…

I found the video series [3] in the latter particularly interesting in trying to understand it, if you’re game to sit through a few hours of live stream.

[1] - (rust) https://github.com/dkellner/chronofold

[2] - (js) https://github.com/jmatsushita/purescript-chronofold

[3] https://m.youtube.com/watch?v=gg5q_V7tBjE&pp=sAQA

omgtehlion2• 5 years ago

unfortunately, [1] has incorrect behavior on some inputs. The hard part of the algo - integration - is implemented incorrectly there :(

and for [2] it is still an "open question", as per their Readme.

joseluis2• 5 years ago

then would you mind opening an issue in the first repository so that it can have a chance to be fixed?

howolduis2• 5 years ago

how about opening an issue instead of complaining?

jitl3• 5 years ago

Here’s a presentation by Grischenko on Chronofold https://m.youtube.com/watch?v=dKzMZsg5EVA

tcldr• 5 years ago

CRDTs are fascinating data structures to me. One question: how would you handle something like cursor position with a DS like this? In the structure itself or a parallel structure with the site-id, insertion-point and expiration date?

lewisjoe• 5 years ago

Cursor positions are nothing but a counter. And counters are CRDTs by default, which means they are associative, idempotent and transitive. Best way is to have them as a separate structure pointing to an index.

Chronofold: A data structure for versioned text (2020)

Related Stories