Hedtke, Moritz (2024)
Optimizing Collaborative Plain Text Editing Algorithms for Decentralized Non-Realtime Text Editing.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00027834
Bachelor Thesis, Primary publication, Publisher's Version
Text
Bachelor_Thesis_Optimizing_Collaborative_Plain_Text_Editing_Algorithms.pdf Copyright Information: CC BY 4.0 International - Creative Commons, Attribution. Download (2MB) |
Item Type: | Bachelor Thesis |
---|---|
Type of entry: | Primary publication |
Title: | Optimizing Collaborative Plain Text Editing Algorithms for Decentralized Non-Realtime Text Editing |
Language: | English |
Date: | 19 September 2024 |
Place of Publication: | Darmstadt |
Collation: | 69 Seiten |
DOI: | 10.26083/tuprints-00027834 |
Abstract: | Text editing is ubiquitous, as it occurs on almost every website, mobile app, and desktop application. Collaborative text editing avoids manual synchronization when working together with others on text. This requires algorithms that can efficiently combine the concurrent edit operations in an intent-preserving way. Additionally, supporting a wide range of network scenarios enables offline work in a decentralized manner with better availability and reliability than with central servers. In this thesis, we first look at prior solutions for plain text editing and their ability to preserve user intentions, as users should not experience unexpected behavior when concurrently editing text. Then, we improve the benchmarking approach of prior research to estimate asymptotic complexity and to measure performance of algorithmic edge cases. Based on that, we propose optimizations for a prior collaborative text editing algorithm called Fugue. Our optimized algorithm can handle character insertion and deletion in logarithmic runtime in relation to the text length and with constant memory usage per character operation. It uses 25 bytes and one microsecond per operation on four Intel Xeon Gold vCPUs for a representative text with 25 million operations. We also develop a local web application as a proof of concept for working on plain text collaboratively using WebRTC. Additionally, we show that the maximally non-interleaving property in the Fugue paper can exhibit interleaving when deletions are involved. |
Status: | Publisher's Version |
URN: | urn:nbn:de:tuda-tuprints-278347 |
Classification DDC: | 000 Generalities, computers, information > 004 Computer science |
Divisions: | 20 Department of Computer Science > Software Technology |
Date Deposited: | 19 Sep 2024 08:21 |
Last Modified: | 20 Sep 2024 09:56 |
URI: | https://tuprints.ulb.tu-darmstadt.de/id/eprint/27834 |
PPN: | 521591384 |
Export: |
View Item |