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!1 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.
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. ↩