Composition in State-based Replicated Data Types

Abstract

Keeping replicated data strongly consistent is convenient when communication
is fast and available. In internet-scale distributed systems the
reality of high communication latencies and likelihood of partitions, leads
developers to adopt more relaxed consistency models, such as eventual consistency.
Conflict-free Replicated Data Types, bring structure to the design
of eventually consistent data management solutions, by precisely describing
the behaviour under concurrent updates and guarantying a path to reconciliation.
This paper oers a survey of the mathematical structures that support
state based multi-master replication with reconciliation, and shows how state
structures and state transformations can be composed to provide data types
that are now used in practice in many geo-replicated systems.