The distributed deadlock detection algorithm described in the title is an improved version of Obermarck’s algorithm [1]. One change is associating a lock history with each transaction. The lock history records all locks held or requested by the transaction, and moves with the transaction from site to site. Another change divides resources into two types, depending on whether the resource’s lock granularity and mode can be determined from remote sites or only at the site of the resource. A three-part algorithm is presented whose first two parts take advantage of these changes to minimize the number of intersite messages. The third part of the algorithm is basically the same as Obermarck’s. An informal proof of correctness is included, although for the general case the paper simply refers to Obermarck’s proof [1].

The advantage of the algorithm is its ability to detect the most frequent deadlocks with a minimum (often none) of intersite messages. In the most general case, the algorithm requires no more messages than [1]. The tradeoff cost is the overhead due to the lock histories.

Though not exceptional, the presentation is direct and straightforward. An understanding of the algorithm is aided by two detailed examples. An appendix, however, suffers from inadequate explanation. From a series of diagrams using an undocumented (and confusing to this reviewer) notation, a formula for the number of deadlocks of cycle length two is deduced. A fuller justification would have been helpful.