Article

Download article

Review of joint text editing algorithms Conflict-free Replicated Data Types (CRDT)

Yurii Rabeshko, Yurii Turbal

Received 04.09.2023, Revised 10.11.2023, Accepted 18.12.2023

Abstract

Analysing and selecting algorithms for collaborative text editing, especially implementing conflict-free replicated data types, is critical to understanding how modern systems can achieve real-time collaboration while ensuring data integrity. The purpose of the study is to review various collaborative editing algorithms and conduct a comparative analysis to understand their advantages, disadvantages, and applications. Statistical methods, methods for analysing algorithms and their use in real-world scenarios are used. The study results showed that the use of collaborative text editing algorithms contributes to solving important tasks and challenges in the modern world of information technology. Collaborative editing algorithms are determined to facilitate realtime communication and information exchange. This is especially important in the context of remote work and communication, which have become the standard for many organisations. Collaborative text editing is widely used in various fields and industries where teamwork, real-time collaboration, and document sharing are essential, such as scientific research, education, software development, book and manuscript editing, legal cooperation, contract draughting, medical reports, etc. In addition, using optimised collaborative editing algorithms helps reduce the time required to process data and create text materials. Collaborative editing algorithms have a wide range of applications in research, business, and education. They allow teams and individual users to solve problems more efficiently and work together on projects. The ability to use the results obtained in practical activities will allow using algorithms for joint text editing for further innovation and development of information technologies, which will allow working together and exchanging information with the whole world in real-time

Keywords:

distributed systems; key operations; Logoot; Astrong; Logarithmic Sequence; Replicated Growable Array

https://doi.org/10.62660/2306-4412.4.2023.10-18

Retrieved from Volume 28, No. 4, 2023

Pages 10-18

References Suggested citation

References

[1] Alsulami, N., Cherif, A., & Imine, A. (2022). Collaborative editing over opportunistic networks. International Journal of Ad Hoc and Ubiquitous Computing, 39(3), 141-156. doi: 10.1504/IJAHUC.2022.121121.

[2] Attiya, H., Burckhardt, S., Gotsman, A., Morrison, A., Yang, H., & Zawirski, M. (2016). Specification and complexity of collaborative text editing. In Proceedings of the 2016 ACM symposium on principles of distributed computing (pp. 259-268). New York: Association for Computing Machinery. doi: 10.1145/2933057.2933090.

[3] Brahneborg, D., Afzal, W., & Mubeen, S. (2022). Resilient conflict-free replicated data types without atomic broadcast. In Proceedings of the 17th international conference on software technologies (pp. 516-523). Lisbon: SciTePress. doi: 10.5220/0011314500003266.

[4] Cai, W., He, F., & Lv, X. (2022). Multi-core accelerated CRDT for large-scale and dynamic collaboration. The Journal of Supercomputing, 78, 10799-10828. doi: 10.1007/s11227-022-04308-7.

[5] David, I., & Syriani, E. (2022). Real-time collaborative multi-level modeling by conflict-free replicated data types. Software and Systems Modeling, 22, 1131-1150. doi: 10.1007/s10270-022-01054-5.

[6] GitHub. (2016). Retrieved from https://github.com/hugooliveirad/elm-logoot.

[7] GitHub. (2021). Retrieved from https://github.com/josephg/simple-crdt-text.

[8] Gomes, V.B., Kleppmann, M., Mulligan, D.P., & Beresford, A.R. (2017). Verifying strong eventual consistency in distributed systems. Proceedings of the ACM on Programming Languages, 1, article number 109. doi: 10.1145/3133933.

[9] Hu, F., & Trivedi, R.H. (2020). Mapping hotel brand positioning and competitive landscapes by text-mining usergenerated content. International Journal of Hospitality Management, 84, article number 102317. doi: 10.1016/j. ijhm.2019.102317.

[10] Jacob, F., Bayreuther, S., & Hartenstein, H. (2021). On conflict-free replicated data types and equivocation in byzantine setups. arXiv - CS - Distributed, Parallel, and Cluster Computing, 1. doi: 10.48550/arXiv.2109.10554.

[11] Kyrychek, H.H., & Chubich, A.I. (2020). Kanban-method use for software development organization. Scientific notes of Taurida National V.I. Vernadsky University. Series: Technical Sciences, 31(6), 78-82. doi: 10.32838/TNU2663-5941/2020.6-1/13.

[12] Kleppmann, M., Mulligan, D.P., Gomes, V.B.F., & Beresford, A.R. (2021). A highly-available move operation for replicated trees. IEEE Transactions on Parallel and Distributed Systems, 33(7), 1711-1724. doi: 10.1109/ TPDS.2021.3118603.

[13] Kleppmann, M., Wiggins, A., van Hardenberg, P., & McGranaghan, M. (2019). Local-first software: You own your data, in spite of the cloud. In Proceedings of the 2019 ACM sigplan international symposium on new ideas, new paradigms, and reflections on programming and software (pp. 154-178). New York: Association for Computing Machinery. doi: 10.1145/3359591.3359737.

[14] Medvedovska, O., & Yatsenko, V. (2021). Cloud services for organization of joint work on documents in real time mode. Bulletin of the Cherkasy Bohdan Khmelnytsky National University. Series “Pedagogical Sciences”, 1, 112-121. doi: 10.31651/2524-2660-2021-1-112-121.

[15] Nédelec, B., Molli, P., Mostefaoui, A., & Desmontils, E. (2013). LSEQ: An adaptive structure for sequences in distributed collaborative editing. In Proceedings of the 2013 ACM symposium on document engineering (pp. 37-46). New York: Association for Computing Machinery. doi: 10.1145/2494266.2494278.

[16] Nicolas, M., Oster, G., & Perrin, O. (2020). Efficient renaming in sequence CRDTs. In proceedings of the 7th workshop on principles and practice of consistency for distributed data (pp. 1-8). New York: Association for Computing Machinery. doi: 10.1145/3380787.3393682.

[17] Karayel, E., & Gonzàlez, E. (2022). Strong eventual consistency of the collaborative editing framework WOOT. Distributed Computing, 35, 145-164. doi: 10.1007/s00446-021-00414-6.

[18] Roh, H.G., Jeon, M., Kim, J.S., & Lee, J. (2011). Replicated abstract data types: Building blocks for collaborative applications. Journal of Parallel and Distributed Computing, 71(3), 354-368. doi: 10.1016/j.jpdc.2010.12.006.

[19] Saquib, N., Krintz, C., & Wolski, R. (2022). Ordering operations for generic replicated data types using version trees. In Proceedings of the 9th workshop on principles and practice of consistency for distributed data (pp. 39-46). New York: Association for Computing Machinery. doi: 10.1145/3517209.3524038.

[20] Shchetynina, O., Kravchenko, N., Horbatiuk, L., Alieksieieva, H., & Mezhuyev, V. (2022). Trello as a tool for the development of lifelong learning skills of senior students. Postmodern Openings, 13(2), 143-167. doi: 10.18662/ po/13.2/447.

[21] Weiss, S., Urso, P., & Molli, P. (2009). Logoot: A scalable optimistic replication algorithm for collaborative editing on P2P networks. In 29th IEEE international conference on distributed computing systems (pp. 404-412). Montreal: IEEE. doi: 10.1109/ICDCS.2009.75.

Suggested citation

Rabeshko, Yu. , & Turbal , Yu. (2023). Review of joint text editing algorithms Conflict-free Replicated Data Types (CRDT). Bulletin of Cherkasy State Technological University, 28(4), 10-18. https://doi.org/10.62660/2306-4412.4.2023.10-18