CRDTs for Fonto

Bachelor thesis (2020)

Authors

M.C.H. Li Electrical Engineering, Mathematics and Computer Science
W.H. Wang Electrical Engineering, Mathematics and Computer Science
C. van Rijn Electrical Engineering, Mathematics and Computer Science
Q.C.L. Lee Electrical Engineering, Mathematics and Computer Science

Contributors

B.H.M. Gerritsen Computer Science & Engineering-Teaching Team - EEMCS (supervisor 1)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2020 Martin Li, Wang Hao Wang, Cas van Rijn, Quentin Lee
More Info
expand_more

Published Date

07-07-2020

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Recent times once more informed us on the relevance of capable online collaborative tools. For our online collaborative XML editor, we have looked into technologies for constrained block editing which, obeying schemas such as with XML, permit on- and offline users or agents to add, delete, copy, move, split and merge blocks of text. To that end, we studied the current state of Operational Transformations (OT) and Conflict-free Replicated Data Types (CRDT). Furthermore, after selection of the best-ranking enabling technology, we studied existing CRDT implementations for unstructured texts, and extended a Logoot-based CRDT to implement on-and offline split and merge block support. We designed a proof of concept and created a scientific prototype to deliver a proof of concept stability, reproducibility and convergence. For now, we excluded undo and redo operations. Given these conditions, we deliver emperical evidence of our implementation to converge under all circumstances, including split and acyclic block mergers. Finally, we give an outlook and design recommendations for production implementations, and suggestions for tackling the problem of cyclic references in block mergers.