Abstract

The problem of deadlock detection in a distributed system has been extensively studied in the past few years. Many algorithms on distributed deadlock detection have been proposed under the assumption that the processors and communication in the system are fault-free. However, in an unreliable distributed system, faulty processors may prevent a deadlock detection algorithm from properly detecting deadlocks. Few of the algorithms proposed in the literature address the issue of handling process failures in a distributed system. This paper proposes a fault-tolerant distributed deadlock detection algorithm which integrates a priority-based probe algorithm with a PMC-based diagnosis model. This algorithm detects deadlock cycles as well as identifies process failures under a bounded number of failures in a deadlock cycle by using extended probe messages that contain additional information about faulty processors. We present this algorithm, give an informal proof, and discuss its run time complexity.

Department(s)

Computer Science

Comments

The first Author is a Graduate Student,

This work was supported in part by the National Science Foundation under Grant Number MSS-9216479, and, in part, from the Air Force Office of Scientific Research under contract number F49620-92-J-0546.

Keywords and Phrases

Fault-tolerant algorithms, distributed deadlock detection, deadlock resolution, distributed algorithms, distributed systems, fault diagnosis

Report Number

CSc-92-04

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1992 University of Missouri - Rolla, All rights reserved

Publication Date

15 October, 1992

Download

Share

 
COinS