1. 12

“Despite decades of research and practical experience, developers have few tools for programming reliable distributed applications without resorting to expensive coordination techniques. Conflict-free replicated datatypes (CRDTs) are a promising line of work that enables 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.”


    1. [Comment removed by author]

    2. 1

      CALM (see, for example, “Keeping CALM: when distributed consistency is easy”, https://arxiv.org/pdf/1901.01930.pdf) is one of the most useful theoretical ideas in distributed systems. Monotonicity is a super powerful tool for thinking about the kinds of calculations and updates that can be done without coordination, which is useful for stuff like this (reasoning about readers in an eventually consistent database), and for related problems like HPC and writing multithreaded programs.

      The work in this paper interests me because, while CRDTs provide a really nice mental model for writers and for what happens in the database at rest, its much less clear what they mean for readers and what happens in the database during an interleaved stream of updates and reads. There’s been some other work on this (e.g. somebody pointed me at ElectricSQL, which I haven’t looked at yet), but I really like this angle.

      1. 1

        I’ve printed that paper out and it’s on my TODO list.

        I enjoyed the paper in the OP - thought I will admit to not liking their categorisation of sequential consistency and above as ‘safe’ with below being ‘unsafe’.