Comparing How Atomicity Mechanisms Support Replication

CMU-CS-85-123

Maurice Herlihy

May 1985

Most pessimistic mechanisms for implementing atomicity in distributed systems fall into three broad categories: two-phase locking schemes, timestamping schemes, and hybrid schemes employing both locking and timestamps. This paper proposes a new criterion for evaluating these mechanisms: the constraints they impose on the availability of replicated data.

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. Constraints on quorum assignment determine the range of availability properties realizable by a replication method.

This paper compares the constraints on quorum assignment necessary to maximize concurrency under generalized locking, timestamping, and hybrid concurrency control mechanisms. This comparison shows that hybrid schemes impose weaker constraints on availability then timestamping schemes, and locking schemes impose constraints incomparable to those of the others. Because hybrid schemes permit more concurrency than locking schemes, these results suggest that hybrid schemes are preferable to the others for ensuring atomicity in highly available and highly concurrent distributed systems.

19 pages

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

This page maintained by reports@cs.cmu.edu