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
fDate :
12/1/1989 12:00:00 AM
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;
Journal_Title :
Software Engineering, IEEE Transactions on