Managing update conflicts in Bayou, a weakly connected replicated storage system

Abstract

Bayou is a replicated, weakly consmtent storage system designed for a mobile computing environment that includes portable machines with less than ideal network connectivity. To maximize availabdity, users can read and write any accessible replica. Bayou's design has focused on supporting apphcation-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 confhct 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, mchrding 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.