Presentation: CRDTs and the Quest for Distributed Consistency

I've been at the University of Cambridge, doing research full time now, which is really cool, I get to go deep into interesting topics. Most of my work there has been on CRDTs, which is what I shall talk about in the talk. That is, data structures which can be modified on several different devices at the same time by several different users, and they automatically ensure a good degree of consistency. If people are editing stuff at the same time, they ensure that everyone ends up with the same document on their screen at the end. The structural integrity of the document is maintained.

A lot of what I've been thinking about is how would you take various different kinds of applications and model them on top of CRDTs. If you want to make a spreadsheet or a CAD application for designing industrial power plants or whatever, how would you model that kind of data in a way that several people can work on it at the same time using CRDTs? That's something that the existing implementations haven't really looked at.

One that I have been working on for months, and now finally I have a solution to, is the following: if you have something like JSON, which you can represent as a tree, you can imagine wanting to move a sub-tree around. You take some object tree that is in one place and move it somewhere else. In a graphics application you get that kind of operation all the time. Even in a rich text word processor you have those kind of tree operations: for example, you can imagine taking up a paragraph and turning it into a bulleted list. What you are doing is you're creating a new bulleted list sub-tree, and then moving that paragraph to be a child of that list. These kinds of operations are really useful, but they are really difficult to make consistent. Users can move things around arbitrarily at the same time, and you can get tricky edge-cases. Imagine you have a tree with A and B as siblings, and that one user moves A to be a child of B. And another user concurrently moves B to be a child of A. Each tree is moved to be a child of the other one. If you’re not careful, you end up with a loop where two nodes become dependent on each other, and detached from the rest of the tree, so that they just disappear. Those are the kinds of problems that arise.

I think that's the motivation for why we want to build applications in this way in the first place. At the moment it's really simple to build centralized applications, where you just have a single server in charge of making the decisions. But for business purposes it would actually be really valuable to have applications where the data is more controlled by the end-user devices. What I'm thinking here is — let's say some software service application is developed by a startup. If a business wants to start using this application then they're totally dependent on that startup’s continued existence. And I like to remind people that there is no such thing as the cloud — it’s just using somebody else's computer. With CRDTs we can start building applications where more happens on the client side.

There may still be a cloud component, but we can make it optional, we can reduce the dependence on it. The recent CPU bug, Meltdown, showed us that the isolation between different users in multi-tenant cloud systems is maybe not that perfect. I think that the fewer secrets we can put in the cloud, the better. CRDTs work nicely with end-to-end encryption, so we can have encrypted data stored in cloud services without any plain text being visible to the cloud services. They only store encrypted data. The security angle is not the main thrust of this talk but I think it's another good additional motivation.