Using Type Information to Enhance the Availability of Partitioned Data

CMU-CS-85-119

Maurice Herlihy

April 1985

A partition occurs when functioning sites in a distributed system are unable to communicate. This paper introduces a new method for managing replicated data in the presence of partitions. A novel aspect of this method is that it systematically exploits type-specific properties of the data to support better availability and concurrency than comparable methods in which operations are classified only as reads or writes. Each activity has an associated level, which governs how it is serialized with respect to other activities. Activities at the same level are serialized dynamically, but higher-level activities are serialized after lower-level activities. A replicated data item is a typed object that provides a set of operations to its clients. A quorum for an operation is any set of sites whose co-operation suffices to execute that operation, and a quorum assignment associates a set of quorums with each operation. Higher-level activities executing "in the future" may use different quorum assignments than lower-level activities executing "in the past." Following a failure, an activity that is unable to make progress using one quorum assignment may switch to another by restarting at a different level.

27 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]