Tech Report CS-91-27

Conflict, Queueing, and Deadlocks in Cooperative Transaction Hierarchies

Marian H. Nodine

April, 1991


Cooperative transaction hierarchies are a model for transactions on databases that support design applications. This model relaxes the atomicity constraint, allowing controlled interactions among different cooperative transactions.

This work summarizes earlier work in [NSFZ90], and describes the nature of conflict and queueing in the context of that work. Since queueing can cause deadlocks, we discuss the nature of deadlocks in a cooperative transaction hierarchy, and propose an algorithm for deadlock detection. We give some pointers on how to resolve deadlocks. We also show that determining deadlock freedom, which would be preferable to deadlock detection, is co-NP-hard.

(complete text in pdf)