Algorithms for Consistency in Optimistically Replicated File Systems

Management of related, replicated objects is often fundamental to the design of reliable distributed systems. We are concerned both with the objects themselves: propagation of updates and reclamation of storage; as well as management of the possibly replicated directories used to keep track of and find the objects. This paper presents a family of algorithms for use in managing replicated objects and the accompanying graph structured directory systems. Members of this family are presented in order of increasing power and flexibility, followed by discussion of their correctness. The use of the algorithms in a replicated file system context is outlined throughout the presentation. 1 Introduction Desires to improve availability and performance of information serves to motivate replicating information at locations "closer" to the data's intended This work was sponsored by DARPA under contract number F29601-87-C-0072. y This author is also affiliated with Locus Computing Corporation. u..