Edge locks and deadlock avoidance in distributed systems

Abstract

Two locking protocols are defined for distributed database systems. One protocol provides deadlock avoidance without the need to roll back transactions. The other allows a useful weakening of the protocol in which only a limited class of easily handled deadlocks may occur. The protocols are capable of handling replicated as well as partitioned data. Like the centralized protocol on which they are based, the protocol of this paper permits locking at multiple granularities and allows collections of locks to be constructed to correspond to an arbitrary collection of database operations. Special provisions are made in the protocol to allow readers, and in particular, readers that touch data at only one site, to execute with less locking overhead than writers. Following the description of the protocol, comparisons are made between the protocol of this paper and other protocols previously published that offer similar features.