ABSTRACT
M athias W eske Hasso Plattner Institute at University o f Potsdam Potsdam, Germany.
A bstract Synchronization of concurrent transactions in database systems using the well-known 2-phase-locking protocol may result in waiting conditions in volving database transactions and, in case of circular waiting conditions, deadlock. All transactions involved in a deadlock come to a halt, a clearly very undesirable situation. In this chapter, the deadlock problem in database systems is characterized using a set of generic deadlock conditions. We show th a t a set of transactions encounter a deadlock situation if these con ditions are met. In general, there are fundamentally different approaches to deadlock handling: deadlock prevention, deadlock avoidance, and deadlock detection. We discuss algorithms for each of these approaches. Finally, deadlock detection in distributed database systems is treated in more de tail. In distributed database systems transactions may span multiple sites. Hence, distributed deadlocks cannot be detected using local knowledge of one site only; on the contrary, sites have to communicate according to dead lock detection algorithms, to identify distributed deadlock cycles, and to resolve them allowing transactions to resume operation. In this chapter, the deadlock problem in distributed database systems is introduced, and a set of algorithms to detect and resolve distributed deadlocks are presented.