Lehrstuhl für Dialogorientierte Systeme

Deadlock Detection Agents (DDAs)


Involved


Description

We have developed 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. 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.

To compare the performance of the DDA scheme and other deadlock detection algorithms we have implemented a simulation system simulating a distributed system of autonomous object managers. So far we have compared the DDA approach to a so-called edge-chasing distributed deadlock detection approach, the one that seems to induce the lowest number of messages within this class of algorithms. The two algorithms perform alike for system loads with a low conflict rate while the DDA approach outperforms the other algorithm when loads with high conflict probabilities are considered.

To further show the practicability of the DDA approach we are currently implementing the timeout approach and a representative of the path-pushing algorithms.


The papers can be found at:

Lehrstuhl für Dialogorientierte Systeme Projects MailContact us
Stefan Pröls, 19.05.1996