Recurse Center

Paper of the Week: Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System

David Albert

This is part of our “Paper of the Week” series. For more info, check out our introductory blog post.

This week’s paper is Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System by Douglas B. Terry, Marvin M. Theimer, Karin Petersen, Alan J. Demers, Mike J. Spreitzer and Carl H. Hauser. It was written at Xerox’s Palo Alto Research Center and presented at SOSP ‘95, the ACM Symposium on Operating Systems Principles.

This week’s paper was submitted by Hacker Schooler Maggie Zhou, who shared the following:

Designing a storage system in the face of bad networks and update conflicts, are still problems today (see: the network is (not) reliable). Bayou presents an early example of designing in the face of network partition and conflicting, concurrent updates. It was the first systems paper I got through and really made me want to read more.

Here’s the abstract from the paper:

Bayou is a replicated, weakly consistent storage system designed for a mobile computing environment that includes portable machines with less than ideal network connectivity. To maximize availability, users can read and write any accessible replica. Bayou’s design has focused on supporting application-specific mechanisms to detect and resolve the update conflicts that naturally arise in such a system, ensuring that replicas move towards eventual consistency, and defining a protocol by which the resolution of update conflicts stabilizes. It includes novel methods for conflict detection, called dependency checks, and per-write conflict resolution based on client-provided merge procedures. To guarantee eventual consistency, Bayou servers must be able to rollback the effects of previously executed writes and redo them according to a global serialization order. Furthermore, Bayou permits clients to observe the results of all writes received by a server, including tentative writes whose conflicts have not been ultimately resolved. This paper presents the motivation for and design of these mechanisms and describes the experiences gained with an initial implementation of the system.

Read Along

Read Along is a way for you to participate in Paper of the Week. If you want to take part, all you have to do is read the paper, make something small in response (code or prose), and email us a link to what you made by noon Eastern Time next Monday.

Last week’s paper was Out of the Tar Pit. Here are the Read Along submissions:

  • Igor Bondarenko wrote a reflection on how the paper’s proposed Functional Relational Programming system relates to some current ideas in UI programming.
  • Dan Luu, a Hacker School alum, takes issue with the paper’s claim that informal reasoning is more important than testing.

We also had one more Read Along submission for the Chubby paper from two weeks ago:

Happy reading!