Marc Shapiro

"Consistency without concurrency control in large, dynamic system"

A Commutative Replicated Data Type (CRDT) is one where all concurrent operations commute. The replicas of a CRDT converge automatically, without complex concurrency control.

I will describe Treedoc, a non-trivial CRDT design, supporting the abstraction of a totally-ordered sequence. Two essential properties are that the identifiers of Treedoc atoms do not change with concurrent updates, and that they are selected from a dense space. The design shows that garbage collection is an important and difficult issue in CRDTs.

We validated the Treedoc design with performance measurements in the context of Wikipedia. I will discuss how to eliminate a the scalability bottleneck of garbage collection: to avoid a system-wide consensus, we propose a flexible two-tier architecture and a protocol for migrating between tiers. We also discuss how the CRDT concept can be generalised, and its limitations.