Consistency for mutable shared data in scalable, available, fault-tolerant, decentralized applications

Replicating shared data is a fundamental mechanism in large-scale distributed systems, but suffers from a fundamental tension between scalability and data consistency. Eventual consistency sidesteps the (foreground) synchronisation bottleneck, but remains ad-hoc, error-prone, and difficult to prove correct.

In this talk, I will introduce a promising approach that is simple, scales almost indefinitely, and provably ensures eventual consistency: A CRDT is a data type that demonstrates some simple properties, that its concurrent operations commute, or that its states form a semi-lattice. Any CRDT provably converges, provided all replicas eventually receive all operations. A CRDT requires no synchronisation: an update can execute immediately, irrespective of network latency, faults, or disconnection; it is highly scalable and fault-tolerant.

This is joint work with Marek Zawirski and Marc Shapiro of LIP6, Nuno Preguica and Sérgio Duarte of Universidade Nova de Lisboa, and Carlos Baquero, of Universidade do Minho.