416 Distributed Systems: Project ideas

Winter 2016

This page presents three project ideas that you can choose to satisfy the project requirement for the course. Below I sketch out each of projects. However, note that these are not intended to be complete: a key piece of the project is to come up with your own system specification and design; you would still need to do this for the projects below.

RPC Chains

An advanced and flexible abstraction for remote computation; an alternative to RPC.

In class and in assignments you learned about RPC, a popular distributed systems abstraction that stood the test of time. A more recent paper (published in 2009) proposes a more flexible alternative, called RPC Chains. The basic idea is to extend the two-point RPC loop with multiple locations that are strung together into a chain. Each location along the RPC chain executes some local procedure. Visually, the standard RPC and RPC chain are summarized in the following illustration:

The paper cited above details a specific (and extensive) design and implementation of an RPC chains systems. For this project you can use this as a starting point for thinking about potential designs. You will have to scope down your implementation to something more feasible.

Conflict-free replicated data types (CRDTs)

Data structure that provides strong eventual consistency.

Distributed state management is one of the most challenging aspects of distributed systems. CRDTs are an abstraction that has nice guarantees in the case where the updates to distributed state cannot be ordered and where replicas of distributed state eventually synchronize. The wikipedia article provides a primer; for more details see the paper by Shapiro et al. The picture below illustrates how the states of three replicas evolve as two of the replicas (at the top) operate on the distributed state.

For this project you should understand the theory behind CRDTs, implement several CRDTs, thoroughly test them, and then build one or two applications that use these CRDTs to do something interesting. You can implement the CRDTs described in the paper above (some are really simple), but you may find it especially interesting to try to design a CRDT of your very own. In this case you would need to also prove that the CRDT satisfies certain properties.