TU Darmstadt / ULB / TUprints

Optimizing Collaborative Plain Text Editing Algorithms for Decentralized Non-Realtime Text Editing

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

[img] 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:
Actions (login required)
View Item View Item