[2002.09511] Chronofold: a data structure for versioned text
source link: https://arxiv.org/abs/2002.09511
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 21 Feb 2020 (v1), last revised 24 Apr 2020 (this version, v4)]
Chronofold: a data structure for versioned text
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK