Deadlock Detection Agents: A Distributed Deadlock Detection Scheme

We describe a new deadlock detection scheme that was devised for a distributed system of autonomously operating object managers. In this system two-phase locking-based synchronization of parallel transactions is done locally---e.g., by employing a semantic locking scheme based on the objects' interface operations. The deadlock detection is enabled by dynamically created deadlock detection agents (DDAs). Transactions start executing without any DDA. Only if a conflict with some other transaction occurs they are associated with a DDA: either a DDA one of the conflicting transactions is already associated with or, if no such DDA exists, a newly created one. If two transactions that are already associated with different DDAs encounter a conflict, their two DDAs are merged into one DDA. The DDA scheme is a ``self-tuning'' system: After an initial warm-up phase, dedicated DDAs will be formed for so-called centers of locality. A dynamic shift in locality of the distributed system will be responded to by automatically creating new DDAs while the obsolete ones terminate. A simulation study indicates the superiority of the DDA scheme over a so-called edge-chasing distributed deadlock detection approach.

You can download the whole postscript file.

Natalija Krivokapic, 12.11.1996;