A Commutative Replicated Data Type for Cooperative Editing
Authors:
- Nuno PreguicaNPNuno Preguica
- Joan Manuel MarquesJMJoan Manuel Marques
- Marc ShapiroMSMarc Shapiro
- Mihai LetiaMLMihai Letia
Top Cited Papers
- 1 June 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636927,p. 395-403
Abstract
A commutative replicated data type (CRDT) is one where all concurrent operations commute. The replicas of a CRDT converge automatically, without complex concurrency control. This paper describes Treedoc, a novel CRDT design for cooperative text editing. An essential property is that the identifiers of Treedoc atoms are selected from a dense space. We discuss practical alternatives for implementing the identifier space based on an extended binary tree. We also discuss storage alternatives for data and meta-data, and mechanisms for compacting the tree. In the best case, Treedoc incurs no overhead with respect to a linear text buffer. We validate the results with traces from existing edit histories.Keywords
This publication has 19 references indexed in Scilit:
- A New Operational Transformation Framework for Real-Time Group EditorsIEEE Transactions on Parallel and Distributed Systems, 2007
- Operation context and context-based operational transformation2006
- Data consistency for P2P collaborative editing2006
- Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems2006
- How to design optimistic operations for peer-to-peer replication2006
- Preserving operation effects relation in group editors2004
- Implementing fault-tolerant replicated objects using Psync2003
- An integrating, transformation-oriented approach to concurrency control and undo in group editors1996
- Semantics-based concurrency controlACM Transactions on Database Systems, 1992
- Commutativity-based concurrency control for abstract data typesIEEE Transactions on Computers, 1988