Marc Shapiro(Université Pierre et Marie Curi)
"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.
|Zeit:||Montag, 11.01.2010, 15.00 Uhr|
|Ort:||Saarbrücken, Wartburg, Raum 410|
|Hinweis:||Der Vortrag wird live nach Kaiserslautern Gebäude 49, Raum 206 übertragen.|