A deadlock detection and resolution algorithm for sequential transaction processing with multiple lock modes

An algorithm for deadlock detection and resolution in sequential transaction processing is presented. Two-phase locking is assumed for ensuring serializability, the lock requests obey the granularity locking protocol, and each granule may be locked in one of the following lock modes: IS, IX, S, SIX and X. For each object, lock requests are honored according to a first-come-first-served basis except for lock conversions. The basic idea for the deadlock detection resolution is in the construction of a new direct graph called a holder/waiter-transaction waited-by graph. The authors establish guidelines for the identification of a victim in a deadlock cycle and propose a resolution algorithm whose time and space requirements are reasonable and whose solution is near optimal