Efficient detection and resolution of OR deadlocks in distributed systems
Autor: | Kil Hong Joo, Soojung Lee |
---|---|
Rok vydání: | 2005 |
Předmět: |
Spanning tree
Wait-for graph Computer Networks and Communications Computer science Distributed computing Edge chasing Parallel computing Deadlock Theoretical Computer Science Tree (data structure) Artificial Intelligence Hardware and Architecture Distributed algorithm Enhanced Data Rates for GSM Evolution Computer Science::Operating Systems Algorithm Deadlock prevention algorithms Software |
Zdroj: | Journal of Parallel and Distributed Computing. 65:985-993 |
ISSN: | 0743-7315 |
Popis: | This paper proposes a distributed algorithm for resolving deadlocks under the OR request model. The algorithm builds a distributed spanning tree by propagating probes. An encoding scheme is devised to deduce the ancestor-descendant relationship between tree nodes, so that the initiator of the algorithm collects only non-tree edge information to detect deadlock, whereas the current algorithms require all the edge information for deadlock detection. The proposed algorithm resolves all deadlocks reachable from the initiator. Its performance in terms of number of messages and execution time is better than or comparable to that of the existing algorithms. We further showed through analytic evaluation that the suggested algorithm substantially shortens deadlock detection time. |
Databáze: | OpenAIRE |
Externí odkaz: |