Deadlock prediction for Escrow transactions

摘要

The Escrow transactional method permits long-lived transactions to update records without blocking concurrent access by other transactions to records modified. A situation may occur in an Escrow system in which an update request cannot currently be granted, but if the requesting transaction is allowed to wait, the resulting situation is safe in the sense of the banker's algorithm, i.e. a schedule to grant requests exists whereby all current requests can be granted. Any algorithm to find such a schedule must predict potential deadlocks, and we show that this problem is NP-complete, using a variant of a proof by Gold. The proof draws an analogy between transactional deadlock prediction and the banker's algorithm, and thus is of independent interest. In the conclusions of Section 5 we point out some basic negative performance ramifications of deadlock avoidance/detection inherent in the standard approach of the banker's algorithm; this suggests an avenue for further research.