composition.al

An introduction to replica conflict resolution

A couple of weeks ago, I had the chance to do a guest lecture in my colleague Peter Alvaro’s undergrad distributed systems course! Peter is well-known as an engaging lecturer — in fact, I’ve been sitting in on his class so I can steal all of his teaching techniques.

So I wasn’t sure if I would be able to measure up to students’ high expectations for his class. But it seemed to go well! I decided I wanted to talk about resolving conflicts between replicas in distributed systems. This was jumping ahead a bit, since Peter hadn’t really started to talk about replication in the course yet, but the students were engaged and asked very good questions.

It just so happened that the day I guest-lectured was the day that a student started making videos of the class, and those videos are now up on YouTube for anyone to watch!

I started out by talking a bit about why we do replication in the first place and how conflicts between replicas arise. Then I talked about application-specific (or “content-aware”, if you like) strategies for resolving those conflicts, using the example of a replicated shopping cart. The class had already covered partial orders in the context of Lamport’s “happens-before” relation, so I was well situated to introduce a little more math: upper bounds, least upper bounds, and join-semilattices.

A lot of partial orders are join-semilattices, but some aren’t! So we talked about that, and I brought it back to distributed systems by making the informal claim that, if operations that affect replicas’ states can be thought of as elements of a join-semilattice, then we have a “natural” way of resolving conflicts between replicas.

Afterward, one student delighted me by asking where they could read more about the topic!1 And a few days later, another student shared the beautiful sketchnotes they had made:

Aren’t these students amazing?! I’m stoked about teaching my own version of this course in the spring.

  1. I suggested that they look up conflict-free replicated data types. I didn’t have the presence of mind to suggest it at the time, but this blog post from Michael Arntzenius is also good.

Comments