New paper draft: “Joining Forces”

I’m happy to announce a new draft paper, “Joining Forces: Toward a Unified Account of LVars and Convergent Replicated Data Types”, that my advisor and I just submitted to WoDet 2014. This short paper covers our work in progress on bringing together LVars and CRDTs, CvRDTs in particular.

Update (February 19, 2014): Our paper was accepted at WoDet, and the above link now points to the final version.

Here’s the abstract:

LVars–shared memory locations whose semantics are defined in terms of an application-specific lattice–offer a principled approach to deterministic-by-construction, shared-state parallel programming: writes to an LVar take the join of the old and new values with respect to the lattice, while reads from an LVar can observe only that its contents have crossed a specified threshold in the lattice. This semantics guarantees that programs have a deterministic outcome, despite parallel execution and schedule nondeterminism.

LVars have a close cousin in the distributed systems literature: convergent replicated data types (CvRDTs), which leverage lattice properties to guarantee that all replicas of a distributed object (for instance, in a distributed database) are eventually consistent. Unlike LVars, in which all updates are joins, CvRDTs allow updates that are inflationary with respect to the lattice but do not compute a join. Moreover, CvRDTs differ from LVars in that they allow intermediate states to be observed: if two replicas of an object are updated independently, reads of those replicas may disagree until a (least-upper-bound) merge operation takes place.

Although CvRDTs and LVars were developed independently, LVars ensure determinism under parallel execution by leveraging the same lattice properties that CvRDTs use to ensure eventual consistency. Therefore, a reasonable next research question is: how can we take inspiration from CvRDTs to improve the LVars model, and vice versa? In this paper, we take steps toward answering that question in both directions: we consider both how to extend CvRDTs with LVar-style threshold reads and how to extend LVars with CvRDT-style inflationary updates, and we advocate for the usefulness of these extensions.

Although we’re just getting started with this work, we hope to make more progress and expand this paper to a full-length version sooner or later. Comments and feedback are very welcome!