Replication Methods for Abstract Data Types,
Abstract
An advantage of distributed systems over centralized systems is that valuable data can be stored redundantly at multiple locations--a practica commonly called 'replication'. Replication can enhance the availability of data in the presence of failures, increasing the likelihood that the data will be accessible when needed. This thesis introduces a new method for managing replicated data. We propose new techniques to address four problems associated with replication: the representation and manipulation of replicated data, concurrency control, on-the-fly reconfiguration, and enhancing availability in the presence of partitions. Unlike many methods that support replication only for uninterpreted files, our method makes use of type-specific properties of objects (such as sets, queues, or directories) to provide more effective replication. Associated with each operation of the data type is a set of quorums, which are collections of sites whose cooperation suffices to execute the operation. Analysis of the algebraic structure of the data type is used to derive a set of constraints on quorum intersections. Any choice of quorums that satisfies these constraints yields a correct implementation, and it can be shown that no smaller set of constraints guarantees correctness. By taking advantage of type-specific properties in a general and systematic way, our method can realize a wider range of availability properties, more concurrency, more flexible reconfiguration, and better tolerance of partitions than existing replication methods. Keywords: Atomicity, Availability, Concurrency control, Partitions, Reconfiguration, and Reliability.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1984
- Accession Number
- ADA153648
Entities
People
- M. P. Herlihy
Organizations
- Massachusetts Institute of Technology