Paper Titles
Effect of Initial Lean on Scaling of Postural Feedback Responses
p.142
An Optimal Estimator Model of Multi-Sensory Processing in Human Postural Control
p.148
Production of Novel Exopolysaccharide with Emulsifying Ability from Marine Microorganism, Alteromonas sp. Strain 00SS11568
p.155
The Roles of Specific Residues on ERK2 for Nuclear Translocation in Response to Nerve Growth Factors in PC12 Cells
p.162
A Hybrid Algorithm for Fast Detection and Resolution of Generalized Deadlocks in Distributed Systems
p.171
Development of High-Performance Ultra-Small Size RF Chip Inductors for Wireless Communication System Application
p.177
Utilization of Markov Random Field for Large Images: Multiframe Work and Bayesian Approach
p.183
X-Ray Image Analysis Based on Fractal Dimension
p.189
Real Time Evaluation of Overseas Technology Trend Information
p.193

A Hybrid Algorithm for Fast Detection and Resolution of Generalized Deadlocks in Distributed Systems

Article Preview

Abstract:

In the literature only a handful of studies have been performed on the distributed deadlock problem in the generalized request model. Most of those algorithms use either the diffusing computation technique or have the initiator collect all the dependency information among processes. This paper proposes an algorithm which incorporates these two methods with the following properties: first, it removes the reduction phase of the diffusing computation; second, it encodes the dependency information to reduce message length, rather than transmitting it naively as is. The main advantage of the proposed algorithm is that deadlock detection time is reduced to almost half of that of the existing algorithms.

You might also be interested in these eBooks
On the Convergence of Bio-, Information-, Enrivonmental-, Energy-, Space- and Nano-Technolgies View Preview

Info:

Periodical:

Key Engineering Materials (Volumes 277-279)

Pages:

171-176

DOI:

https://doi.org/10.4028/www.scientific.net/KEM.277-279.171

Citation:

Cite this paper

Online since:

January 2005

Authors:

Soo Jung Lee, Kwang Moon Cho

Keywords:

Deadlock Detection, Deadlock Resolution, Distributed Deadlocks, Distributed System, Generalized Model

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2005 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

References

[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, (1974).

Google Scholar

[2] G. Bracha and S. Toueg. A distributed algorithm for generalized deadlock detection. Distributed Computing, 2: 127-138, (1987).

DOI: 10.1007/bf01782773

Google Scholar

[3] J. Brzezinski, J. M. Helary, M. Raynal, and M. Singhal. Deadlock models and a general algorithm for distributed deadlock detection. Journal of Parallel and Distributed Computing, 31(2): 112-125, (1995).

DOI: 10.1006/jpdc.1995.1150

Google Scholar

[4] S. Chen, Y. Deng, and P. Attie. Deadlock detection and resolution in distributed systems based on locally constructed wait-for graphs. Tech. Report, School of Computer Science, Florida Inter-national University, Aug. (1995).

DOI: 10.1109/icdcs.1996.508012

Google Scholar

[5] E. W. Dijkstra and C. S. Scholten. Termination detection for diffusing computations. Information Processing Letters, 11(1): 1-4, Aug. (1980).

DOI: 10.1016/0020-0190(80)90021-6

Google Scholar

[6] A. D. Kshemkalyani and M. Singhal. Efficient detection and resolution of generalized distributed deadlocks. IEEE Transactions on Software Engineering, 20(1): 43-54, Jan. (1994).

DOI: 10.1109/32.263754

Google Scholar

[7] A. D. Kshemkalyani and M. Singhal. A one-phase algorithm to detect distributed deadlocks in replicated databases. IEEE Transactions on Knowledge and Data Engineering, 11(6): 880-895, Nov/Dec (1999).

DOI: 10.1109/69.824601

Google Scholar

[8] S. Lee. Efficient generalized deadlock detection and resolution in distributed systems. IEEE International Conference on Distributed Computing Systems, pp.47-56, Apr. (2001).

DOI: 10.1109/icdsc.2001.918932

Google Scholar

[9] S. Lee. A hybrid algorithm for fast detection and resolution of generalized deadlocks in distributed systems. Tech. Rep. 2003-5, Dept. of Computer Education, GyeongIn National Univ. of Education, (2003).

Google Scholar

[10] M. Singhal. Deadlock detection in distributed systems. IEEE Computer, 22: 37-48, (1989).

Google Scholar