On deadlocks of exclusive AND-requests for resources
Tóm tắt
Although there are numerous concurrency control algorithms and they use a variety of techniques, there is an underlying serializability theory that serves both as a basis for analyzing their correctness and as a guide for designing new protocols. Following this paradigm, this paper proposes a uniform framework for characterizing and developing distributed deadlock-related algorithms. The system considered here consists of processes making multiple requests for exclusive access to resources. The results examine the role of process abortion and the asymmetry between processes and resources. To illustrate the generality of the framework, the results are used to analyze several well-known deadlock detectors, thus revealing a common structure among them, despite the variety of techniques they use.
Tài liệu tham khảo
Badal DZ: The distributed deadlock detection algorithm. ACM Trans Comput Syst 4(4): 320–337 (1986)
Bar-Noy A, Dolev D: Shared-memory vs. Message-passing in an asynchronous distributed environment. Proc ACM Symp Principles of Distributed Computing, Edmonton, Alberta (Aug. 1989), pp 307–318
Bernstein PA, Goodman N: Concurrency control in distributed database systems. ACM Comput Surv 13(2): 185–221 (1981)
Bernstein PA, Hadzilacos V, Goodman N: Concurrency control and recovery in database systems. Addison-Wesley, Reading, Massachusetts, 1987
Bracha G, Toueg S: Distributed deadlock detection. Distrib Comput 2: 127–138 (1987)
Chandy KM, Lamport L: Distributed snapshots: determining global states of distributed systems. ACM Trans Comput Syst 3(1): 63–75 (1985)
Chandy KM, Misra J: A distributed algorithm for detecting resource deadlocks in distributed systems. Proc ACM Symp Principles of Distributed Computing, Ottawa, Ontario (Aug. 1982), pp 157–164
Chandy KM, Misra J, Haas LM: Distributed deadlock detection. ACM Trans Comput Syst 1(2): 144–156 (1983)
Cidon I, Jaffe JM, Sidi M: Local distributed deadlock detection by cycle detection and clustering. IEEE Trans Softw Eng SE-13, 1: 3–14 (1987)
Dijkstra EW, Scholten CS: Predicate calculus and program semantics. Springer Berlin Heidelberg New York, (1989).
Eswaran KP, Gray JN, Lorie RA, Traiger IL: The notions of consistency and predicate locks in a database system. Commun ACM 19(11): 624–633 (1976)
Gries D, Schneider FB: A logical approach to discrete math. Springer, Berlin Heidelberg New York, 1994
Gurevich Y: Logic activities in Europe. SIGACT News 25 (2): 11–24 (1994)
Havender VW: Avoiding deadlock in multitasking. IBM Syst J 2: 74–84 (1968)
Ho GS, Ramamoorthy CV: Protocols for deadlock detection in distributed database systems. IEEE Trans Softw Eng SE-8, 6: 554–557 (1982)
Huang ST: A distributed deadlock detection algorithm for CSP- like communication. ACM Trans Program Lang Syst 12(1): 102–122 (1990)
Knapp E: Deadlock detection in distributed database. ACM Comput Surv 19(4): 303–328 (1987)
Kshemkalyani AD, Singhal M: Correct two-phase and one- phase deadlock detection algorithms for distributed systems. Proc IEEE Symp Parallel and Distributed Processing, Dallas, Texas (Dec. 1990), pp 126–129
Lamport L: Time, clocks, and the ordering of events in a distributed system. Commun ACM 21(7): 558–565 (1978)
Marzullo K, Sabel L: Using consistent subcuts for detecting stable properties. Proc WDAG ’91, Delphi, Greece (Oct 1991), pp 273–288
Mattern F: Virtual time and global states of distributed systems. In: Cosnard M et al (eds) Parallel and distributed algorithms. North-Holland (1989), pp 215–226
Minoura T: Deadlock avoidance revisited. J ACM 29(4): pp 1023–1048 (1982)
Mitchell DP, Merritt MJ: A distributed algorithm for deadlock detection and resolution. Proc ACM Symp Principles of Distributed Computing, Vancouver, British Columbia (Aug. 1984), pp 282–284
Obermarck R: Distributed deadlock detection algorithm. ACM Trans Database Syst 7(2): 187–208 (1982)
Papadimitriou CH: The theory of database concurrency control. Computer Science Press, Rockville, Maryland, 1986
Reddy PK, Bhalla S: Deadlock prevention in a distributed database system. SIGMOD Record 22(3): 40–46 (1993)
Rosenkrantz DJ, Stearns RE, Lewis II PM: System level concurrency control for distributed database systems. ACM Trans Database Systems 3(2): 178–198 (1978)
Rukoz M: Hierarchical deadlock detection for nested transactions. Distrib Comput 4: 123–129 (1991)
Sanders BA, Heuberger PA: Distributed deadlock detection and resolution with probes. Proc Int Conf Distributed Algorithms (Sept. 1989), LNCS 392, Springer, Berlin Heidelberg New York, pp 207–218
Sinha MK, Natarajan N: A priority based distributed deadlock detection algorithm. IEEE Trans Softw Eng SE-11 (1): 67–80 (1985)
Tay YC: What is a deadlock? In: Cosnard M, Puigjaner R (eds). Decentralized and distributed systems. Elsevier, Amsterdam, pp 49–60, 1993
Toueg S, Ullman JD: Deadlock-free packet switching networks. SIAM J Comput 10: 594–611 (1981)
Valiant L: A bridging model for parallel computation. Commun ACM 33(8): 103–111 (1990)
Wuu GT, Bernstein AJ: False deadlock detection in distributed systems. IEEE Trans Softw Eng SE-11, 8: 820–821 (1985)