Efficient detection and resolution of OR deadlocks in distributed systems |
| |
Affiliation: | 1. Department of Mathematics and Computer Science, University of Groningen, The Netherlands;2. Department of Applied Informatics, University of Macedonia, Thessaloniki, Greece;3. Department of Computer Science and Software Engineering, University of Canterbury, Christchurch, New Zealand;1. Kelley School of Business, Indiana University, United States;2. HSBC Business School, Peking University, China |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|