Collaborative text editing and versioning is known to be a tough topic. Diffs, OT and CRDT are three relevant classes of algorithms which all have their issues. CRDT is the only one that works correctly and deterministically in a distributed environment, at the unfortunate cost of data structure complexity and metadata overheads. A chronofold is a data structure for editable linear collections based on the Causal Tree CRDT model. A chronofold maintains time-ordering and space-ordering of its elements. Simply put, a it is both a log and a text at the same time, which makes it very convenient for text versioning and synchronization. Being a simple array-based data structure with O(1) insertions, chronofold makes CRDT overheads acceptable for many practical applications .
Chronofold is a replicated data structure for versioned text, based on the extended Causal Tree model. 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 .
R
Collaborative text editing and versioning is known to be a tough topic. Diffs, OT and CRDT are three relevant classes of algorithms which all have their issues. CRDT is the only one that works correctly and deterministically in a distributed environment, at the unfortunate cost of data structure complexity and metadata overheads. A chronofold is a data structure for editable linear collections
Chronofold is a replicated data structure for versioned text,
R
Causal Tree CRDT model. A chronofold maintains time-ordering and space-ordering of its elements. Simply put, a it is both a log and a text at the same time, which makes it very convenient for text versioning and synchronization. Being a simple array-based data structure with O(1) insertions, chronofold makes CRDT overheads acceptable for many practical applications
extended Causal Tree model. 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