This repository contains tests for a particular edge case that occurs in collaborative text editing CRDTs. The tests consist of two replicas, both of which initially start with the two-character string:
<>
On one replica, the string is edited by inserting a sequence of hyphens between the two angle brackets:
<---------->
At the same time, on the other replica, a sequence of hash signs are inserted in the same place:
<##########>
Finally, the two replicas merge, and we inspect the outcome.
In some editing algorithms, the merged result is always either <----------##########> or
<##########---------->. However, in some other algorithms the insertions may be interleaved,
resulting in a final string such as <#---##--###--##---##>.
This interleaving behaviour can be problematic. Imagine two users each inserted several paragraphs of text at the same place in a document. If the merged result is a character-by-character random interleaving of those paragraphs, the outcome is likely to be an unreadable jumble of letters, which is probably not what the users wanted.
This repository contains Java implementations of several collaborative editing algorithms by Ahmed-Nacer et al [1]. The included algorithms are Logoot [9, 10], RGA [6], SOCT2 [7], WOOT [4], WOOTO [8], and WOOTH [1].
To compile the Java algorithms and execute the interleaving tests, install Maven, and then you can run:
$ mvn compile exec:java -Dexec.mainClass=jbenchmarker.Interleaving
Moreover, this repository contains a JavaScript test for the implementation of the LSEQ algorithm by Nédelec et al [2, 3]. The code of this implementation is hosted on npm. To download the code and run the test, install Node.js, and then run:
$ npm install
$ node lseq-test.js
The current tests observe the interleaving anomaly in Logoot, SOCT2, and LSEQ. They do not observe interleaving in RGA, WOOT, WOOTO, or WOOTH. Obviously, the test cannot prove that interleaving will never occur in those algorithms.
The Java implementations of Logoot, RGA, SOCT2, WOOT, WOOTO, and WOOTH were developed by Mehdi Ahmed-Nacer, Gérald Oster, Pascal Urso (judging by the @author tags in the code), and released at https://github.com/PascalUrso/ReplicationBenchmark under the GPLv3 license.
The JavaScript implementation of LSEQ was developed by "Chat-Wane" (presumably Brice Nédelec?), and released at https://github.com/Chat-Wane/LSEQTree under the MIT license.
The interleaving tests (lseq-test.js and src/jbenchmarker/Interleaving.java) and this README
were developed by Martin Kleppmann, and released under the
GPLv3 license for license compatibility with the above.
Literature references:
-
Mehdi Ahmed-Nacer, Claudia-Lavinia Ignat, Gérald Oster, Hyun-Gul Roh, and Pascal Urso: “Evaluating CRDTs for real-time document editing,” at 11th ACM Symposium on Document Engineering (DocEng), pages 103–112, September 2011. doi:10.1145/2034691.2034717
-
Brice Nédelec, Pascal Molli, Achour Mostefaoui, and Emmanuel Desmontils: “LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing,” at 13th ACM Symposium on Document Engineering (DocEng), pages 37–46, September 2013. doi:10.1145/2494266.2494278
-
Brice Nédelec, Pascal Molli, and Achour Mostefaoui: “CRATE: Writing Stories Together with our Browsers,” at 25th International World Wide Web Conference (WWW), pages 231–234, April 2016. doi:10.1145/2872518.2890539
-
Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine: “Data consistency for P2P collaborative editing,” at ACM Conference on Computer Supported Cooperative Work (CSCW), pages 259–268, November 2006. doi:10.1145/1180875.1180916
-
Nuno Preguiça, Joan Manuel Marques, Marc Shapiro, and Mihai Letia: “A Commutative Replicated Data Type for Cooperative Editing,” at 29th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 395–403, June 2009. doi:10.1109/ICDCS.2009.20
-
Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, and Joonwon Lee: “Replicated abstract data types: Building blocks for collaborative applications,” Journal of Parallel and Distributed Computing, volume 71, number 3, pages 354–368, March 2011. doi:10.1016/j.jpdc.2010.12.006
-
Maher Suleiman, Michèle Cart, and Jean Ferrié: “Serialization of concurrent operations in a distributed collaborative environment,” at International Conference on Supporting Group Work (GROUP), pages 435–445, November 1997. doi:10.1145/266838.267369
-
Stéphane Weiss, Pascal Urso, and Pascal Molli: “Wooki: A P2P Wiki-Based Collaborative Writing Tool,” at 8th International Conference on Web Information Systems Engineering (WISE), pages 503–512, December 2007. doi:10.1007/978-3-540-76993-4_42
-
Stéphane Weiss, Pascal Urso, and Pascal Molli: “Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks,” at 29th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 404–412, June 2009. doi:10.1109/ICDCS.2009.75
-
Stéphane Weiss, Pascal Urso, and Pascal Molli: “Logoot-Undo: Distributed Collaborative Editing System on P2P Networks,” IEEE Transactions on Parallel and Distributed Systems, volume 21, number 8, pages 1162–1174, January 2010. doi:10.1109/TPDS.2009.173