Detail

CRDTs: Consistency without concurrency control

A CRDT is a data type whose operations commute when they are concurrent.
Replicas of a CRDT eventually converge without any complex concurrency control or the need for any centralized component. This makes CRDTs very appealing for managing data in large-scale environments, such as cloud computing
or web-based environments because it ensures convergence without complex synchronization or reconciliation.
In this talk we will present Treedoc, a CRDT for cooperative text editing.
Treedoc relies on the use of unique identifiers selected from a dense space. We discuss two practical alternatives for implementing the identifier space based on an extended binary tree.
We will also present an optimization to the basic design to address scalability issues, based on restructuring the tree without violating commutativity. This optimization allows to support disconnected nodes.