Abstract
Collaborative applications are becoming more prevalent for a variety of reasons, most important of which is the increased interest in remote work. In addition to adapting the business processes to a remote setting, designers of collaborative software have to decide on how their software can be used collaboratively. This paper discusses the two main technologies used to enable network-based real- or near-real-time collaborative software, namely Operational Transformation and Conflict-free Replicated Data Types. Recent developments in each technology are discussed, as well as a brief overview of their theoretical underpinnings.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Liu, E.: A CRDT-based file synchronization system (2021). https://ntnuopen.ntnu.no/ntnu-xmlui/handle/11250/2778095. Accessed 06 Nov 2021
Harris, J.: What’s different about the new Google Docs? Google Drive Blog (11 May 2010). https://drive.googleblog.com/2010/05/whats-different-about-new-google-docs.html. Accessed 27 Nov 2021
Ellis, C.A., Gibbs, S.J.: Concurrency control in groupware systems. In: Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, New York, NY, USA, Jun 1989, pp. 399–407 (1989). https://doi.org/10.1145/67544.66963
Sun, C., Ellis, C.: Operational transformation in real-time group editors: issues, algorithms, and achievements. In: Proceedings of the 1998 ACM Conference on Computer Supported Cooperative Work, New York, NY, USA, Nov 1998, pp. 59–68 (1998). https://doi.org/10.1145/289444.289469
Preguica, N., Marques, J.M., Shapiro, M., Letia, M.: A commutative replicated data type for cooperative editing. In: 2009 29th IEEE International Conference on Distributed Computing Systems, Montreal, Quebec, Canada, Jun 2009, pp. 395–403 (2009). https://doi.org/10.1109/ICDCS.2009.20
Weiss, S., Urso, P., Molli, P.: Logoot: a scalable optimistic replication algorithm for collaborative editing on P2P networks. In: 2009 29th IEEE International Conference on Distributed Computing Systems, Jun 2009, pp. 404–412 (2009). https://doi.org/10.1109/ICDCS.2009.75
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978). https://doi.org/10.1145/359545.359563
Sun, C., Sun, D., Ng, A., Cai, W., Cho, B.: Real Differences between OT and CRDT under a general transformation framework for consistency maintenance in co-editors. In: Proceedings of the ACM on Human-Computer Interaction, vol. 4, no. GROUP, Art. no. GROUP (Jan 2020). https://doi.org/10.1145/3375186
Nichols, D.A., Curtis, P., Dixon, M., Lamping, J.: High-latency, low-bandwidth windowing in the Jupiter collaboration system. In: Proceedings of the 8th Annual ACM Symposium on User Interface and Software Technology, New York, NY, USA (Dec 1995), pp. 111–120. https://doi.org/10.1145/215585.215706
Sun, C., Jia, X., Zhang, Y., Yang, Y., Chen, D.: Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. CACM Trans. Comput.-Hum. Interact. 5(1), 63–108 (1998). https://doi.org/10.1145/274444.274447
Sun, C., Sosič, R.: Optimal locking integrated with operational transformation in distributed real-time group editors. In: Proceedings of the Eighteenth annual ACM Symposium on Principles of Distributed Computing, New York, NY, USA, May 1999, pp. 43–52 (1999). https://doi.org/10.1145/301308.301322
Sun, C., Xia, S., Sun, D., Chen, D., Shen, H., Cai, W.: Transparent adaptation of single-user applications for multi-user real-time collaboration. ACM Trans. Comput. Hum. Interact. 13(4), 531–582 (2006). https://doi.org/10.1145/1188816.1188821
Liu, A.F., Xia, S., Shen, H., Sun, C.: CoMaya: incorporating advanced collaboration capabilities into 3d digital media design tools. In: Proceedings of the 2008 ACM Conference on Computer Supported Cooperative Work, New York, NY, USA, Nov 2008, pp. 5–8 (2008). https://doi.org/10.1145/1460563.1460566
Prakash, A., Knister, M.J.: “A framework for undoing actions in collaborative systems. CACM Trans. Comput. Hum. Interact. 1(4), 295–330 (1994). https://doi.org/10.1145/198425.198427
Sun, C.: Undo any operation at any time in group editors. In: Proceedings of the 2000 ACM Conference on Computer Supported Cooperative Work, New York, NY, USA, Dec 2000, pp. 191–200 (2000). https://doi.org/10.1145/358916.358990
Li, D., Li, R.: An admissibility-based operational transformation framework for collaborative editing systems. Comput. Support. Coop. Work 19(1), 1–43 (2010). https://doi.org/10.1007/s10606-009-9103-1
Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M.: Conflict-free replicated data types, Report, Jul 2011. https://hal.inria.fr/inria-00609399. Accessed 08 Jan 2022
Kleppmann, M.: Designing data-intensive applications: the big ideas behind reliable, scalable, and maintainable systems, 1st edn. O’Reilly Media, Boston (2017)
Bailis, P., Ghodsi, A.: Eventual consistency today: limitations, extensions, and beyond: how can applications be built on eventually consistent infrastructure given no guarantee of safety? Queue 11(3), 20–32 (2013). https://doi.org/10.1145/2460276.2462076
van Steen, M., Tanenbaum, A.S.: Distributed Systems, 3rd edn., Version 3.01. Erscheinungsort nicht ermittelbar: Maarten van Steen (2017)
Lamport, L., Malkhi, D., Zhou, L.: Vertical Paxos and primary-backup replication. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing - PODC’09, Calgary, AB, Canada, (2009), p. 312. https://doi.org/10.1145/1582716.1582783
Ongaro, D., Ousterhout, J.: In search of an understandable consensus algorithm. In: Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference, USA, Jun 2014, pp. 305–320 (2014)
Casino, F., Dasaklis, T.K., Patsakis, C.: A systematic literature review of blockchain-based applications: current status, classification and open issues. Telemat. Inform. 36, 55–81 (2019). https://doi.org/10.1016/j.tele.2018.11.006
Finlow-Bates, K.: Adding Trust to CAP: Blockchain as a strong eventual consistency recovery strategy, Sep 2017, p. 12. (2017). https://www.chainfrog.com/wp-content/uploads/2017/09/CAP-paper.pdf
Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, Cambridge (2002). https://doi.org/10.1017/CBO9780511809088. Accessed 08 Jan 2022
Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M.: A comprehensive study of convergent and commutative replicated data types, Report, Inria–Centre Paris-Rocquencourt; INRIA (2011). https://hal.inria.fr/inria-00555588. Accessed 14 Jan 2022
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Hassan, S.A., Abdelbaki, N. (2023). A Survey of Concurrency Control Algorithms in Collaborative Applications. In: Hassanien, A.E., Snášel, V., Tang, M., Sung, TW., Chang, KC. (eds) Proceedings of the 8th International Conference on Advanced Intelligent Systems and Informatics 2022. AISI 2022. Lecture Notes on Data Engineering and Communications Technologies, vol 152. Springer, Cham. https://doi.org/10.1007/978-3-031-20601-6_28
Download citation
DOI: https://doi.org/10.1007/978-3-031-20601-6_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20600-9
Online ISBN: 978-3-031-20601-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)