CMSC 818e Day 10

October 03, 2018

These are notes taken during CMSC 818e: Distributed And Cloud-Based Storage Systems. Course webpage and syllabus here.

The Algorithm Becomes the Teacher

October 02, 2018

What if the value of new scientific contributions was measured not in novelty or performance, but in understandability? This question, raised in “In Search of an Understandable Consensus Algorithm,” for me calls to mind Richard Feynman’s approach to learning and teaching; namely, that if you couldn’t explain an advanced principle of Physics to a freshman, you didn’t really understand it yet yourself.

The Pains of Bureaucracy

September 30, 2018

Proposed in 1989 and now used in many production systems (e.g. Chubby, Spanner, Ceph, Neo4j) the Paxos algorithm is a method for reaching consensus between replicas in a distributed system. At a very high level, the algorithm is simple; replicas can ask to coordinate, or grant promises to be coordinated; they can broadcast values to be accepted, and either acknowledge or reject those values. Conceptually, this mainly just requires that all replicas know how many total replicas there are in the system, so there’s a shared understanding of what it takes to make consensus. If a majority of replicas accept a value, that’s consensus, and the value is committed. The algorithm is used by each replica to independently construct and maintain an identical log of values, which can then be used to construct and maintain consistent data across all of the replicas. However, the algorithm is not at all simple in it’s execution, as is clear from reading Paxos Made Live - An Engineering Perspective by Tushar Chandra, Robert Griesemer, and Joshua Redstone. In this post I’ll discuss their paper along with the ePaxos paper, which presents a different approach.

CMSC 818e Day 8

September 26, 2018

These are notes taken during CMSC 818e: Distributed And Cloud-Based Storage Systems. Course webpage and syllabus here.

Nuts and Bolts Consistency

September 25, 2018

In “Bolt-on Causal Consistency,” Bailis et al. show that it’s possible to upgrade the consistency guarantees of existing eventually consistent data stores by implementing a “shim” layer between the database and the user-facing application. Instead of interacting directly with the database, the application interacts with the shim, and the shim talks to the database on their behalf, restricting reads and writes to ensure causal consistency.