DocumentCode :
1554636
Title :
Sufficient condition for a communication deadlock and distributed deadlock detection
Author :
Wójcik, Barbara E. ; Wójcik, Zbigniew M.
Author_Institution :
Beechcraft Co., Wichita, KS, USA
Volume :
15
Issue :
12
fYear :
1989
fDate :
12/1/1989 12:00:00 AM
Firstpage :
1587
Lastpage :
1595
Abstract :
The necessary and sufficient condition for deadlock in a distributed system and an algorithm for detection of a distributed deadlock based on the sufficient condition are formulated. The protocol formulated, checks all wait-for contiguous requests in one iteration. A cycle is detected when a query message reaches the initiator. A wait-for cycle is only the necessary condition for the distributed deadlock. A no-deadlock message is expected by the query initiator to infer a deadlock-free situation if at least one wait-for cycle is present. A no-deadlock message is issued by a dependent (query intercessor) that is not waiting-for. No no-deadlock message implies a deadlock, and processes listed in the received query messages are the processes involved in a distributed deadlock. Properties of the protocol are discussed. The authors show that a replication of a requested higher-priority (or older) process can prevent a distributed deadlock (in a continuous deadlock treatment). A replication is shown to recover (in a periodical deadlock handling) a sequence of processes from an indefinite wait-die scheme
Keywords :
distributed processing; system recovery; communication deadlock; deadlock-free situation; distributed deadlock detection; indefinite wait-die scheme; no-deadlock message; periodical deadlock handling; protocol; query initiator; query intercessor; query message; replication; sufficient condition; wait-for contiguous requests; wait-for cycle; Computer science; Hardware; Imaging phantoms; Mathematics; Network servers; Protocols; Resource management; Statistics; Sufficient conditions; System recovery;
fLanguage :
English
Journal_Title :
Software Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
0098-5589
Type :
jour
DOI :
10.1109/32.58770
Filename :
58770
Link To Document :
بازگشت