Comparing how atomicity mechanisms support replication
Maurice P. Herlihy · 1985
Most pessimistic mechanisms for implementing atomicity in distributed systems fall into three broad categories: twophase 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 realizc, ole by a replication method, This peper 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 ~eaker constraints on availability than timestamping schemes, and locking schemes impose constraints incompar,able to those of the others.Because hybrid schemes permit more concurrency than locking schemes, these resets sugge.,~tthat hybrid schemes are preferable to the others for ensuring atomicity in highly available and highly conc~urrent distributed systems.