nach oben

Erschienen in:

2013 | OriginalPaper | Buchkapitel

15. Distributed Deadlock Detection

verfasst von : Michel Raynal

Erschienen in: Distributed Algorithms for Message-Passing Systems

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This chapter addresses the deadlock detection problem. After having introduced the AND deadlock model and the OR deadlock model, it presents distributed algorithms that detect their occurrence. Let us recall that the property “there is a deadlock” is a stable property (once deadlocked, a set of processes remain deadlocked until an external agent—the underlying system—resolves it). Hence, as seen in Sect. 6.5, algorithms computing global states of a computation can be used to detect deadlocks. Differently, the algorithms presented in this chapter are specific to deadlock detection. For simplicity, they all assume FIFO channels.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Distributed Termination Detection

Nächstes Kapitel Atomic Consistency (Linearizability)

61.

G. Bracha, S. Toueg, Distributed deadlock detection. Distrib. Comput. 2(3), 127–138 (1987) MATHCrossRef

65.

J. Brzezinski, J.-M. Hélary, M. Raynal, M. Singhal, Deadlock models and a general algorithm for distributed deadlock detection. J. Parallel Distrib. Comput. 31(2), 112–125 (1995) (Erratum printed in Journal of Parallel and Distributed Computing, 32(2), 232 (1996)) CrossRef

76.

K.M. Chandy, J. Misra, Deadlock absence proof for networks of communicating processes. Inf. Process. Lett. 9(4), 185–189 (1979) MathSciNetMATHCrossRef

81.

K.M. Chandy, J. Misra, L.M. Haas, Distributed deadlock detection. ACM Trans. Comput. Syst. 1(2), 144–156 (1983) CrossRef

97.

E.G. Coffman Jr., M.J. Elphick, A. Shoshani, System deadlocks. ACM Comput. Surv. 3(2), 67–78 (1971) MATHCrossRef

115.

E.W.D. Dijkstra, C.S. Scholten, Termination detection for diffusing computations. Inf. Process. Lett. 11(1), 1–4 (1980) MathSciNetMATHCrossRef

160.

V.D. Gligor, S.H. Shattuck, Deadlock detection in distributed systems. IEEE Trans. Softw. Eng. SE-6(5), 435–440 (1980) CrossRef

163.

D. Gray, A. Reuter, Transaction Processing: Concepts and Techniques (Morgan Kaufmann, San Mateo, 1993), 1060 pages. ISBN 1-55860-190-2 MATH

165.

H.N. Haberman, Prevention of system deadlocks. Commun. ACM 12(7), 373–377 (1969) CrossRef

166.

J.W. Havender, Avoiding deadlocks in multitasking systems. IBM Syst. J. 13(3), 168–192 (1971)

169.

J.-M. Hélary, C. Jard, N. Plouzeau, M. Raynal, Detection of stable properties in distributed systems, in Proc. 6th ACM Symposium on Principles of Distributed Computing (PODC’87) (ACM Press, New York, 1987), pp. 125–136

188.

R.C. Holt, Comments on prevention of system deadlocks. Commun. ACM 14(1), 36–38 (1871) CrossRef

206.

P. Knapp, Deadlock detection in distributed databases. ACM Comput. Surv. 19(4), 303–328 (1987) CrossRef

215.

A.D. Kshemkalyani, M. Singhal, Invariant-based verification of a distributed deadlock detection algorithm. IEEE Trans. Softw. Eng. 17(8), 789–799 (1991) CrossRef

216.

A.D. Kshemkalyani, M. Singhal, Efficient detection and resolution of generalized distributed deadlocks. IEEE Trans. Softw. Eng. 20(1), 43–54 (1994) CrossRef

218.

A.D. Kshemkalyani, M. Singhal, A one-phase algorithm to detect distributed deadlocks in replicated databases. IEEE Trans. Knowl. Data Eng. 11(6), 880–895 (1999) CrossRef

248.

D. Manivannan, M. Singhal, An efficient distributed algorithm for detection of knots and cycles in a distributed graph. IEEE Trans. Parallel Distrib. Syst. 14(10), 961–972 (2003) CrossRef

259.

D. Menasce, R. Muntz, Locking and deadlock detection in distributed database. IEEE Trans. Softw. Eng. SE-5(3), 195–202 (1979) CrossRef

260.

J.R. Mendívil, F. Fariña, C.F. Garitagoitia, C.F. Alastruey, J.M. Barnabeu-Auban, A distributed deadlock resolution algorithm for the AND model. IEEE Trans. Parallel Distrib. Syst. 10(5), 433–447 (1999) CrossRef

264.

J. Misra, K.M. Chandy, A distributed graph algorithm: knot detection. ACM Trans. Program. Lang. Syst. 4(4), 678–686 (1982) MATHCrossRef

266.

D.P. Mitchell, M. Merritt, A distributed algorithm for deadlock detection and resolution, in Proc. 3rd ACM Symposium on Principles of Distributed Computing (PODC’84) (ACM Press, New York, 1984), pp. 282–284 CrossRef

278.

N. Nararajan, A distributed scheme for detecting communication deadlocks. IEEE Trans. Softw. Eng. 12(4), 531–537 (1986) CrossRef

287.

R. Obermarck, Distributed deadlock detection algorithm. ACM Trans. Database Syst. 7(2), 197–208 (1982) CrossRef

308.

M. Raynal, Networks and Distributed Computation: Concepts, Tools and Algorithms (The MIT Press, Cambridge, 1987), 168 pages. ISBN 0-262-18130-4

331.

D.J. Rosenkrantz, R.E. Stearns, P.M. Lewis, System level concurrency control in distributed databases. ACM Trans. Database Syst. 3(2), 178–198 (1978) CrossRef

346.

M. Singhal, Deadlock detection in distributed systems. IEEE Comput. 22(11), 37–48 (1989) CrossRef

379.

J. Villadangos, F. Fariña, J.R. Mendívil, C.F. Garitagoitia, A. Cordoba, A safe algorithm for resolving OR deadlocks. IEEE Trans. Softw. Eng. 29(7), 608–622 (2003) CrossRef

389.

H. Wu, W.-N. Chin, J. Jaffar, An efficient distributed deadlock avoidance algorithm for the AND model. IEEE Trans. Softw. Eng. 28(1), 18–29 (2002) CrossRef

391.

G.T.J. Wuu, A.J. Bernstein, False deadlock detection in distributed systems. IEEE Trans. Softw. Eng. SE-11(8), 820–821 (1985) CrossRef

Titel: Distributed Deadlock Detection
verfasst von: Michel Raynal
Verlag: Springer Berlin Heidelberg
Buch: Distributed Algorithms for Message-Passing Systems
Print ISBN: 978-3-642-38122-5

Electronic ISBN: 978-3-642-38123-2

Copyright-Jahr: 2013
DOI: https://doi.org/10.1007/978-3-642-38123-2_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"