Keep CALM and CRDT On

Despite decades of research and practical experience, developers have few tools for programming reliable distributed applications without resorting to expensive coordination techniques. Conflictfree replicated datatypes (CRDTs) are a promising line of work that enable coordination-free replication and offer certain eventual consistency guarantees in a relatively simple object-oriented API. Yet CRDT guarantees extend only to data updates; observations of CRDT state are unconstrained and unsafe. We propose an agenda that embraces the simplicity of CRDTs, but provides richer, more uniform guarantees. We extend CRDTs with a query model that reasons about which queries are safe without coordination by applying monotonicity results from the CALM Theorem, and lay out a larger agenda for developing CRDT data stores that let developers safely and efficiently interact with replicated application state. State-Based CRDTs We begin by reviewing the definition of state-based CRDTs. CvRDTs encapsulate the current 𝑠𝑡𝑎𝑡𝑒 of the replica; let the type of 𝑠𝑡𝑎𝑡𝑒 be called 𝑇 . The API for state-based CRDTs contains three classes of methods, all of which run locally on a single replica's state: Merge: merge is a single, required method that takes a value 𝑣 of type 𝑇 as input. It combines 𝑠𝑡𝑎𝑡𝑒 with 𝑣 to generate a value 𝑠𝑡𝑎𝑡𝑒 ′ of type 𝑇 , and updates itself so that 𝑠𝑡𝑎𝑡𝑒 = 𝑠𝑡𝑎𝑡𝑒 ′ . Constraint: the merge function must be ACI. Operations: these are methods that clients use to modify 𝑠𝑡𝑎𝑡𝑒. Constraint: operations must be monotonic with respect to the type 𝑇 . Queries: these are methods that do not modify 𝑠𝑡𝑎𝑡𝑒, but return a result that may be dependent on 𝑠𝑡𝑎𝑡𝑒.