HackerPapers

arXiv:2002.09511cs.DS

Chronofold: a data structure for versioned text

Victor Grishchenko, Mikhail Patrakeev

Abstract

Chronofold is a replicated data structure for versioned text. It is designed for use in collaborative editors and revision control systems. Past models of this kind either retrofitted local linear orders to a distributed system (the OT approach) or employed distributed data models locally (the CRDT approach). That caused either extreme fragility in a distributed setting or egregious overheads in local use. Overall, that local/distributed impedance mismatch is cognitively taxing and causes lots of complexity. We solve that by using subjective linear orders locally at each replica, while inter-replica communication uses a distributed model. A separate translation layer insulates local data structures from the distributed environment. We modify the Lamport timestamping scheme to make that translation as trivial as possible. We believe our approach has applications beyond the domain of collaborative editing.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 4 identifiable commenters in 5 comments across 5 threads, from Jul 2020 to Mar 2026. Found in 6 HN submissions from Apr 2020 to Aug 2021. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. The future of version control 1 comment

    • In 2007 Bram said to me that my Causal Tree algorithm is a variant of weave. Which is broadly correct. In these 20 years, the family of weave-class algos grew quite big. In my 2020 article, I devoted the intro to making their family portrait https://arxiv.org/abs/2002.09511…

      gritzkoView on HNParent context

  2. Faster CRDTs: An Adventure in Optimization 1 comment

    • About a decade ago, I implemented the Causal Tree CRDT (aka RGA, Timestamped Insertion Tree) in regular expressions using a Unicode string as a storage. Later we made a collaborative editor for Yandex based on that code. It used many of the tricks as described in the text, even…

      gritzkoView on HNParent context

  3. Are CRDTs suitable for shared editing? 1 comment
  4. CRDTs: The Hard Parts [video] 1 comment

    • There was a recent post of a series that dives into CRDTs [1] . Someone linked to a paper, Chronofold: a data structure for versioned text [2] dated this April, that attempts to map CRDT semantics onto text editing. It's still on my list. [1]…

      infogulchView on HNParent context

  5. An Introduction to Conflict-Free Replicated Data Types 1 comment

    • After studying [3], I came to the conclusion that the specific CRDTs they attempted to use for Xi editor might be too low level to be useful in building a text editor directly, but that this is not an intrinsic shortcoming of CRDTs. Rather, the kind of automerging behavior of…

      blurbleblurbleView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.