Towards Improved Support for Conflict-Free Replicated Data Types

Abstract

Conflict-free Replicated Data Types (CRDTs) are distributed data types which ensure Strong Eventual Consistency (SEL), and also has properties such as commutativity and idempotence. There are many variations of CRDTs, and the ones we will study are state-based delta CRDTs. State-based CRDTs is a variation where the CRDT instances synchronize by sending their state to each other. An improvement to this is delta CRDTs which is yet another variation where only the difference of mutations is disseminated. We will explore some of the existing CRDTs, but also present some new CRDT designs and their implementations. One of the new CRDTs presented is Causal Length Set (CLSet), which is a simple, yet effective state-based delta CRDT. It does not use dots as causal context as many other CRDTs; it merely uses a single integer. With this minimalist CRDT design, we can achieve both great performance and a small memory footprint. Another CRDT presented is Multiple Value Map (MVMap), a CRDT which focuses on convenience as opposed to performance.