Distributed deadlock detection and resolution algorithm based on a hybrid wait-for graph and probe generation scheme

Young Chul Park*, Peter Scheuermann, Hsiang Lung Tung

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We present a continuous deadlock detection and resolution algorithm in distributed database systems. Our algorithm maintains an augmented transaction wait-for graph at each site and uses a modified priority-based probe generation scheme in order to detect local deadlocks without transmitting any intra-site deadlock detection messages, to minimize the number of inter-site messages sent for detection of global deadlocks and also for the early detection of global deadlocks that might occur in the future without transmitting detection messages repeatedly. The augmented transaction wait-for graph contains, in addition to lock-wait information, information about message-wait relationships among agents of a transaction, probes received from other sites and transitive wait-for relationships among transactions. Global deadlocks are declared whenever a transitive wait-for relationship from an agent of a global transaction is constructed for some agent of the transaction.

Original languageEnglish (US)
Title of host publicationInternational Conference on Information and Knowledge Management, Proceedings
PublisherACM
Pages378-386
Number of pages9
StatePublished - Dec 1 1995
EventProceedings of the 1995 ACM CIKM 4th International Conference on Information and Knowledge Management - Baltimore, MD, USA
Duration: Nov 28 1995Dec 2 1995

Other

OtherProceedings of the 1995 ACM CIKM 4th International Conference on Information and Knowledge Management
CityBaltimore, MD, USA
Period11/28/9512/2/95

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Business, Management and Accounting(all)

Fingerprint Dive into the research topics of 'Distributed deadlock detection and resolution algorithm based on a hybrid wait-for graph and probe generation scheme'. Together they form a unique fingerprint.

Cite this