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.

I guess they heard that @palvaro is lecturing today 🔥 pic.twitter.com/BzudbcvCKs

— Lindsey Kuper (@lindsey) September 28, 2018

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! I suggested that they look up conflict-free replicated data types. And a few days later, another student shared the beautiful sketchnotes they had made:

@tos # 128 Oct. 12th 2018 Lecture 5(6). (thread) pic.twitter.com/dmbkG8mqfO

— ✨romeo (@romeoexists) October 15, 2018

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