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.
展开▼
