the articles

articles.bib

@article{Lv2018novel,
	author = {Lv, Xiao and He, Fazhi and Cheng, Yuan and Wu, Yiqi},
	journal = {Advanced Engineering Informatics},
	year = {2018},
	month = {10},
	pages = {381--391},
	publisher = {Elsevier BV},
	title = {A novel {CRDT}-based synchronization method for real-time collaborative {CAD} systems},
	volume = {38},
	url = {http://dx.doi.org/10.1016/j.aei.2018.08.008},
	doi = {10.1016/j.aei.2018.08.008},
	abstract = {Abstract CRDT (Conflict-free Replicated Data Type) has been proposed as an alternative synchronization mechanism for collaborative text editing systems in recent years. However, CRDT-based synchronization methods for collaborative systems with sophisticated objects, such as collaborative CAD (Co-CAD) systems, are rarely investigated in previous literatures. How well CRDT-based synchronization methods for Co-CAD systems could perform remains unknown. This paper presents a novel CRDT-based synchronization method to maintain eventual consistency for the feature-based CAD model. Firstly, three operation relations are defined as the dependency-conflict relation, the mutual exclusive relation and the compatible relation in context of the feature-based CAD systems. Secondly, a feature-based conflict detection mechanism is proposed to detect the three relations. Thirdly, a feature-based conflict resolution approach under the CRDT framework is presented to solve the conflicts. Fourthly, the time complexity and the space complexity are analyzed in theory. Finally, case studies of collaborative modeling procedures verify the correctness and feasibility of the proposed method.},
}


@inbook{Gao2018New,
	author = {Gao, Liping and Xu, Xiaofang},
	booktitle = {Computer {Supported} {Cooperative} {Work} and {Social} {Computing}},
	year = {2018},
	month = {dec 11},
	pages = {201--212},
	publisher = {Springer Singapore},
	title = {A {New} {Algorithm} for {Real}-{Time} {Collaborative} {Graphical} {Editing} {System} {Based} on {CRDT}},
	url = {http://dx.doi.org/10.1007/978-981-13-3044-5_15},
	doi = {10.1007/978-981-13-3044-5_15},
	abstract = {With the rapid development of collaborative applications, real-time collaborative graphical editing systems will face many new challenges in the future. The key technology to guarantee the correctness in the graphical editing system is consistency maintenance. It is also a core topic in the field of collaborative computing and a basic research in many scientific and engineering collaboration systems. However, over the past years, the complexity of graphics has produced much problems for the real time editing field, including methods of operational transformation (OT) and conflict resolution strategy with multi-version replication, etc. Recently, CRDT (Exchanged Copy Data Type) has been proposed as a new alternative mechanism in collaborative text editing with much higher efficiency. However, the CRDT-based real-time graphics editing system consistency maintenance method has rarely been studied in the previous literature. In the paper, a kind of CRDT algorithm is proposed, and the complex constraint relationship between the graphics and the dynamic rule library is used to divide the graphic operation into operation, which the relevant solutions are given. The algorithm integrates different types of graphics operations for First, the algorithm guarantees the convergence of the coordinated users and maintains the operational intent under the integrated framework. Secondly, a CRDT-based algorithm is designed. Thirdly, the time complexity and space complexity of the put forward algorithm are theoretically analyzed, which is further verified the feasibility of the algorithm. Finally, The direction of future solution is given.},
}


@inproceedings{Lv2017CRDT,
	author = {Lv, Xiao and He, Fazhi and Cai, Weiwei and Cheng, Yuan and Wu, Yiqi},
	booktitle = {Proceedings of the 12th {Chinese} {Conference} on {Computer} {Supported} {Cooperative} {Work} and {Social} {Computing}},
	year = {2017},
	month = {sep 22},
	organization = {ACM},
	title = {CRDT-based {Conflict} {Detection} and {Resolution} for {Massive}-scale {Real}-time {Collaborative} {CAD} systems},
	url = {http://dx.doi.org/10.1145/3127404.3127436},
	doi = {10.1145/3127404.3127436},
	abstract = {With the popularity of big data and cloud computing, collaborative CAD(Co-CAD) systems face the task of massive-scale collaborative design, which brings new challenges in both academia and industry. Firstly, the key challenges for large-scale collaborative CAD design are analyzed. Then, a novel synchronous mechanism is proposed to deal with the key challenges. Some initial case studies demonstrate that the proposed synchronous mechanism is feasible for massive-scale collaborative design.},
}


@inproceedings{Ahmed2011Evaluating,
	author = {Ahmed-Nacer, Mehdi and Ignat, Claudia-Lavinia and Oster, G{\' e}rald and Roh, Hyun-Gul and Urso, Pascal},
	booktitle = {Proceedings of the 11th {ACM} symposium on {Document} engineering},
	year = {2011},
	month = {sep 19},
	organization = {ACM},
	title = {Evaluating {CRDTs} for real-time document editing},
	url = {http://dx.doi.org/10.1145/2034691.2034717},
	doi = {10.1145/2034691.2034717},
	abstract = {Nowadays, real-time editing systems are catching on. Tools such as Etherpad or Google Docs enable multiple authors at dispersed locations to collaboratively write shared documents. In such systems, a replication mechanism is required to ensure consistency when merging concurrent changes performed on the same document. Current editing systems make use of operational transformation (OT), a traditional replication mechanism for concurrent document editing.

Recently, Commutative Replicated Data Types (CRDTs) were introduced as a new class of replication mechanisms whose concurrent operations are designed to be natively commutative. CRDTs, such as WOOT, Logoot, Treedoc, and RGAs, are expected to be substitutes of replication mechanisms in collaborative editing systems.

This paper demonstrates the suitability of CRDTs for real-time collaborative editing. To reflect the tendency of decentralised collaboration, which can resist censorship, tolerate failures, and let users have control over documents, we collected editing logs from real-time peer-to-peer collaborations. We present our experiment results obtained by replaying those editing logs on various CRDTs and an OT algorithm implemented in the same environment.},
}


@inproceedings{Hall2018Causal,
	author = {Hall, Aaron and Nelson, Grant and Thiesen, Mike and Woods, Nate},
	booktitle = {Proceedings of the {ACM} {Symposium} on {Document} {Engineering} 2018},
	year = {2018},
	month = {aug 28},
	organization = {ACM},
	title = {The {Causal} {Graph} {CRDT} for {Complex} {Document} {Structure}},
	url = {http://dx.doi.org/10.1145/3209280.3229110},
	doi = {10.1145/3209280.3229110},
	abstract = {Commutative Replicated Data Types (CRDTs) are an emerging tool for real-time collaborative editing. Existing work on CRDTs mostly focuses on documents as a list of text content, but large documents (having over 7,000 pages) with complex sectional structure need higher-level organization. We introduce the Causal Graph, which extends the Causal Tree CRDT into a graph of nodes and transitions to represent ordered trees. This data structure is useful in driving document outlines for large collaborative documents, resolving structures with over 100,000 sections in less than a second.},
}


@inproceedings{Enes2019Efficient,
	author = {Enes, Vitor and Almeida, Paulo Sergio and Baquero, Carlos and Leitao, Joao},
	booktitle = {2019 {IEEE} 35th {International} {Conference} on {Data} {Engineering} ({ICDE})},
	year = {2019},
	month = {4},
	organization = {IEEE},
	title = {Efficient {Synchronization} of {State}-{Based} {CRDTs}},
	url = {http://dx.doi.org/10.1109/ICDE.2019.00022},
	doi = {10.1109/icde.2019.00022},
	abstract = {To ensure high availability in large scale distributed systems, Conflict-free Replicated Data Types (CRDTs) relax consistency by allowing immediate query and update operations at the local replica, with no need for remote synchronization. State-based CRDTs synchronize replicas by periodically sending their full state to other replicas, which can become extremely costly as the CRDT state grows. Delta-based CRDTs address this problem by producing small incremental states (deltas) to be used in synchronization instead of the full state. However, current synchronization algorithms for delta-based CRDTs induce redundant wasteful delta propagation, performing worse than expected, and surprisingly, no better than state-based. In this paper we: 1) identify two sources of inefficiency in current synchronization algorithms for delta-based CRDTs; 2) bring the concept of join decomposition to state-based CRDTs; 3) exploit join decompositions to obtain optimal deltas and 4) improve the efficiency of synchronization algorithms; and finally, 5) experimentally evaluate the improved algorithms.},
}


@inproceedings{Oster2006Data,
	author = {Oster, G{\' e}rald and Urso, Pascal and Molli, Pascal and Imine, Abdessamad},
	booktitle = {Proceedings of the 2006 20th anniversary conference on {Computer} supported cooperative work},
	year = {2006},
	month = {nov 4},
	organization = {ACM},
	title = {Data consistency for {P2P} collaborative editing},
	url = {http://dx.doi.org/10.1145/1180875.1180916},
	doi = {10.1145/1180875.1180916},
	abstract = {Peer-to-peer (P2P) networks are very efficient for distributing content. We want to use this potential to allow not only distribution but collaborative editing of this content. Existing collaborative editing systems are centralised or depend on the number of sites. Such systems cannot scale when deployed on P2P networks. In this paper, we propose a new model for building a collaborative editing system. This model is fully decentralised and does not depend on the number of sites.},
}


@inproceedings{Ellis1989Concurrency,
	author = {Ellis, C. A. and Gibbs, S. J.},
	booktitle = {Proceedings of the 1989 {ACM} {SIGMOD} international conference on {Management} of data  - {SIGMOD} '89},
	year = {1989},
	organization = {ACM Press},
	title = {Concurrency control in groupware systems},
	url = {http://dx.doi.org/10.1145/67544.66963},
	doi = {10.1145/67544.66963},
	abstract = {Groupware systems are computer-based systems that support two or more users engaged in a common task, and that provide an interface to a shared environment. These systems frequently require fine-granularity sharing of data and fast response times. This paper distinguishes real-time groupware systems from other multi-user systems and discusses their concurrency control requirements. An algorithm for concurrency control in real-time groupware systems is then presented. The advantages of this algorithm are its simplicity of use and its responsiveness: users can operate directly on the data without obtaining locks. The algorithm must know some semantics of the operations. However the algorithm's overall structure is independent of the semantic information, allowing the algorithm to be adapted to many situations. An example application of the algorithm to group text editing is given, along with a sketch of its proof of correctness in this particular case. We note that the behavior desired in many of these systems is non-serializable.},
}


@article{Sun1998Achieving,
	author = {Sun, Chengzheng and Jia, Xiaohua and Zhang, Yanchun and Yang, Yun and Chen, David},
	journal = {ACM Transactions on Computer-Human Interaction},
	number = {1},
	year = {1998},
	month = {3},
	pages = {63--108},
	publisher = {Association for Computing Machinery (ACM)},
	title = {Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems},
	volume = {5},
	url = {http://dx.doi.org/10.1145/274444.274447},
	doi = {10.1145/274444.274447},
	abstract = {Real-time cooperative editing systems allow multiple users to view and edit the same text/graphic/image/multimedia document at the same time for multiple sites connected by communication networks. Consistency maintenance is one of the most significant challenges in designing and implementing real-time cooperative editing systems. In this article, a consistency model, with properties of convergence, causality preservation, and intention preservation, is proposed as a framework for consistency maintenance in real-time cooperative editing systems. Moreover, an integrated set of schemes and algorithms, which support the proposed consistency model, are devised and discussed in detail. In particular, we have contributed (1) a novel generic operation transformation control algorithm for achieving intention preservation in combination with schemes for achieving convergence and causality preservation and (2) a pair of reversible inclusion and exclusion transformation algorithms for stringwise operations for text editing. An Internet-based prototype system has been built to test the feasibility of the proposed schemes and algorithms},
}


@inproceedings{Nicolaescu2016Near,
	author = {Nicolaescu, Petru and Jahns, Kevin and Derntl, Michael and Klamma, Ralf},
	booktitle = {Proceedings of the 19th {International} {Conference} on {Supporting} {Group} {Work}},
	year = {2016},
	month = {nov 13},
	organization = {ACM},
	title = {Near {Real}-{Time} {Peer}-to-{Peer} {Shared} {Editing} on {Extensible} {Data} {Types}},
	url = {http://dx.doi.org/10.1145/2957276.2957310},
	doi = {10.1145/2957276.2957310},
	abstract = {Near real-time collaboration using Web browsers is becoming rapidly more and more popular for many applications such as text editing, coding, sketching and others. These applications require reliable algorithms to ensure consistency among the participating Web clients. Operational Transformation (OT) and more recently Commutative Replicated Data Types (CRDT) have become widely adopted solutions for this kind of problem. However, most existing approaches are non-trivial and require trade-offs between expressiveness, suitable infrastructure, performance and simplicity. The ever growing number of potential use cases, the new possibilities of cutting-edge messaging protocols that shaped the near real-time Web, and the use of N-way communication between clients (e.g. WebRTC), create a need for peer-to-peer algorithms that perform well and are not restricted to only a few supported data types. In this paper, we present YATA, an approach for peer-to-peer shared editing applications that ensures convergence, preserves user intentions, allows offline editing and can be utilized for arbitrary data types in the Web browser. Using Yjs, its open-source JavaScript library implementation, we have evaluated the performance and multiple usage of YATA in Web and mobile browsers, both on test and real-world data. The promising evaluation results as well as the uptake by many commercial vendors and open-source projects indicate a wide applicability of YATA.},
}


@article{Litt2022Peritext,
	author = {Litt, Geoffrey and Lim, Sarah and Kleppmann, Martin and van Hardenberg, Peter},
	journal = {Proceedings of the ACM on Human-Computer Interaction},
	number = {CSCW2},
	year = {2022},
	month = {nov 7},
	pages = {1--36},
	publisher = {Association for Computing Machinery (ACM)},
	title = {Peritext: A {CRDT} for {Collaborative} {Rich} {Text} {Editing}},
	volume = {6},
	url = {http://dx.doi.org/10.1145/3555644},
	doi = {10.1145/3555644},
	abstract = {Conflict-Free Replicated Data Types (CRDTs) support decentralized collaborative editing of shared data, enabling peer-to-peer sharing and flexible branching and merging workflows. While there is extensive work on CRDTs for plain text, much less is known about CRDTs for rich text with formatting. No algorithms have been published, and existing open-source implementations do not always preserve user intent. In this paper, we describe a model of intent preservation in rich text editing, developed through a series of concurrent editing scenarios. We then describe Peritext, a CRDT algorithm for rich text that satisfies the criteria of our model. The key idea is to store formatting spans alongside the plaintext character sequence, linked to a stable identifier for the first and last character of each span, and then to derive the final formatted text from these spans in a deterministic way that ensures concurrent operations commute. We have prototyped our algorithm in TypeScript, validated it using randomized property-based testing, and integrated it with an editor UI. We also prove that our algorithm ensures convergence, and demonstrate its causality preservation and intention preservation properties.},
}


@article{Weiss2010Logoot,
	author = {Weiss, Stephane and Urso, Pascal and Molli, Pascal},
	journal = {IEEE Transactions on Parallel and Distributed Systems},
	number = {8},
	year = {2010},
	month = {8},
	pages = {1162--1174},
	publisher = {{Institute of Electrical and Electronics Engineers (IEEE)}},
	title = {Logoot-{Undo}: Distributed {Collaborative} {Editing} {System} on {P2P} {Networks}},
	volume = {21},
	url = {http://dx.doi.org/10.1109/TPDS.2009.173},
	doi = {10.1109/tpds.2009.173},
	abstract = {Peer-to-peer systems provide scalable content distribution for cheap and resist to censorship attempts. However, P2P networks mainly distribute immutable content and provide poor support for highly dynamic content such as produced by collaborative systems. A new class of algorithms called CRDT (Commutative Replicated Data Type), which ensures consistency of highly dynamic content on P2P networks, is emerging. However, if existing CRDT algorithms support the "edit anywhere, anytime'' feature, they do not support the "undo anywhere, anytime'' feature. In this paper, we present the Logoot-Undo CRDT algorithm, which integrates the "undo anywhere, anytime'' feature. We compare the performance of the proposed algorithm with related algorithms and measure the impact of the undo feature on the global performance of the algorithm. We prove that the cost of the undo feature remains low on a corpus of data extracted from Wikipedia.},
}


@misc{DavidReal,
	author = {{David Sun} and {Chengzheng Sun} and {Agustina} and {Weiwei Cai}},
	title = {Real {Differences} between {OT} and {CRDT} in {Building} {Co}-{Editing} {Systems} and {Real} {World} {Applications}},
	abstract = {OT (Operational Transformation) was invented for supporting real-time co-editors in the late 1980s and has evolved to become a core technique used in today's working co-editors and adopted in major industrial products. CRDT (Commutative Replicated Data Type) for co-editors was first proposed around 2006, under the name of WOOT (WithOut Operational Transformation). Follow-up CRDT variations are commonly labeled as "post-OT" techniques and have made broad claims of superiority over OT solutions, in terms of correctness, time and space complexity, simplicity, etc. Over one decade later, however, OT remains the choice for building the vast majority of co-editors, whereas CRDT is rarely found in working co-editors. Why? To seek truth from facts, we set out to conduct a comprehensive and critical review of representative OT and CRDT solutions and working co-editors based on them. From this work, we have made important discoveries about OT and CRDT, and revealed facts and evidences that refute CRDT claims over OT on all accounts. We present our discoveries in three related and complementary articles.

In prior two articles, we have revealed the similarities of OT and CRDT in following the same general transformation approach in co-editors, and their real differences in correctness and complexity. In this article, we examine the role of building working co-editors in shaping OT and CRDT research and solutions, and consequential differences in the choice between OT and CRDT in real world co-editors and industry products. In particular, we review the evolution of co-editors from research vehicles to real world applications, and discuss representative OT-based co-editors and alternative approaches in industry products and open source projects. Moreover, we evaluate CRDT-based co-editors in relation to published CRDT solutions, and clarify some myths surrounding "peer-to-peer" co-editing.},
}


@misc{StephaneAbstract,
	author = {{Stéphane Martin} and {Mehdi Ahmed-Nacer} and {Pascal Urso}},
	title = {Abstract unordered and ordered trees {CRDT}},
	abstract = {Trees are fundamental data structure for many areas of computer science and system engineering. In this report, we show how to ensure eventual consistency of optimistically replicated trees. In optimistic replication, the different replicas of a distributed system are allowed to diverge but should eventually reach the same value if no more mutations occur. A new method to ensure eventual consistency is to design Conflict-free Replicated Data Types (CRDT). In this report, we design a collection of tree CRDT using existing set CRDTs. The remaining concurrency problems particular to tree data structure are resolved using one or two layers of correction algorithm. For each of these layer, we propose different and independent policies. Any combination of set CRDT and policies can be constructed, giving to the distributed application programmer the entire control of the behavior of the shared data in face of concurrent mutations. We also propose to order these trees by adding a positioning layer which is also independent to obtain a collection of ordered tree CRDTs.},
}


@inproceedings{Liping2017Research,
	author = {Liping, Gao and Xin, Zhang and Qiang, Zhang},
	booktitle = {Proceedings of the 12th {Chinese} {Conference} on {Computer} {Supported} {Cooperative} {Work} and {Social} {Computing}},
	year = {2017},
	month = {sep 22},
	organization = {ACM},
	title = {Research for {Consistency} {Maintenance} of {Real}-time {Collaborative} {Associated} {Graph} {Model} in {The} {Mobile} {Platform}},
	url = {http://dx.doi.org/10.1145/3127404.3127457},
	doi = {10.1145/3127404.3127457},
	abstract = {Real-time collaborative graph editing system is one of the most important branches of collaborative interactive applications in the mobile platform. In a graphical editing system, there are certain constraints and associations between different graphic objects. However, the traditional consistency maintenance algorithm is mainly conducted in the linear document with unconstrained relationships, and only supports three basic operations (Insert, Delete, Update). Based on basic operations (Create, Delete, Update) supported by traditional operation transformation algorithms, this paper extends some operations (Move, Relate, Relieve) which can represent the linkage effect on the location property of graph objects. And the relationship between objects is mapped to the associated graph document model. According to types of concurrent conflict generated by different operation types under the non-linear model, some reasonable conflict solutions are designed to maintain consistency of the shared graphical document under real-time collaborative editing. Besides, when a graphical editing system containing multiple operations types is applied to the mobile platform, the existing optimistic concurrency control algorithm based on stable networks may be not applicable to the new scenario because of the instability of the mobile networks. In view of the characteristics of signal instability in mobile network environment, the traditional OT control algorithm is improved in this paper and new concurrency control is also introduced. Based on the mechanism of sending the re-transmission request for lost operations on the client site and processing it on the server side, the concurrent control algorithm in the mobile platform of unstable network has been designed. The paper develops a mobile collaborative graphics editing system named as Co-Paint, and some simulation test further verify the correctness and feasibility of the above control algorithm and conversion functions.},
}


@inproceedings{Agustina2013Dependency,
	author = {{Agustina} and Sun, Chengzheng},
	booktitle = {Proceedings of the 2013 conference on {Computer} supported cooperative work},
	year = {2013},
	month = {feb 23},
	organization = {ACM},
	title = {Dependency-conflict detection in real-time collaborative 3D design systems},
	url = {http://dx.doi.org/10.1145/2441776.2441856},
	doi = {10.1145/2441776.2441856},
	abstract = {One core issue in real-time collaborative 3D design systems is dependency-conflict caused by concurrent access to object replicas in Dependency Graph (DG) states -- the common underlying structure of 3D design systems. Prior work has provided an Operational Transformation (OT) solution to dependency-conflict resolution, assuming dependency-conflict can be detected. But dependency-conflict detection is a complex and challenging issue because dependency relations among targets of concurrent operations -- a necessary condition for dependency-conflict -- is dynamic in nature and the detection must refer to prior DG states that are often unavailable during dependency-conflict detection. Conflict detection was never a difficult issue in prior OT work based on well-defined linear data models because conflict relations are readily derivable from operation position parameters without having to refer to prior document states. This work is the first to recognize and solve the dependency-conflict detection problem, which complements prior work in dependency-conflict resolution to provide a complete solution to dependency-conflict problem in real-time collaborative DG-based systems. Both theoretical verification and real implementation have been applied to validate the proposed dependency-conflict detection solution.},
}


@article{D2018Spacetime,
	author = {D'Angelo, Gabriele and Di Iorio, Angelo and Zacchiroli, Stefano},
	journal = {Proceedings of the ACM on Human-Computer Interaction},
	year = {2018},
	month = {11},
	pages = {1--19},
	publisher = {Association for Computing Machinery (ACM)},
	title = {Spacetime {Characterization} of {Real}-{Time} {Collaborative} {Editing}},
	volume = {2},
	url = {http://dx.doi.org/10.1145/3274310},
	doi = {10.1145/3274310},
	abstract = {Real-Time Collaborative Editing (RTCE) is a popular way of instrumenting cooperative work on documents, in particular on the Web. Little is known in the literature yet about RTCE usage patterns in the real world. In this paper we study how a popular RTCE editor (Etherpad) is used in the wild, digging into the edit histories of a large collection of documents (about 14 000 pads), retrieved from one of the most popular public instances of the platform, hosted by the Wikimedia Foundation. The pad analysis is supported by a novel conceptual model that allows to label edit operations as "collaborative" or not depending on their distance-in edit position (space), edit time, or spacetime (both)-from edits made by other authors. The model is applied to classify all edits from the pad corpus. Classification results are further used to characterize the collaboration behavior of pad authors. Findings show that: 1) about half of the pads have a single author and hence witnessed no collaboration; 2) collaboration on common document parts happens often, but it happens asynchronously with authors taking turns in editing; and 3) simultaneous editing of common document parts happens very rarely. These findings help in revisiting early RTCE design decisions (e.g., the granularity of conflict management in RTCE protocols) and give insights on how to address novel needs (e.g., end-to-end encryption and offline editing).},
}