Distributed deadlock detection and resolution based on hardwareclocks

摘要

Inexpensive but accurate hardware clocks are now commonplace onmany systems. A clock synchronization protocol can keep the collectionof clocks for a group of networked systems roughly synchronized withoutthe expenditure of a great deal of processor time or network bandwidth.As long as the bounded skew between clocks is taken into account, roughreal time can provide an intuitive and valuable mechanism for providinga notion of order in a distributed system. This paper presents astraightforward token-based protocol for the detection of distributeddeadlock under the single resource model. It uses clock values as tokentime stamps to ensure that exactly one process in a deadlock cycle, theprocess that completed the cycle, detects the deadlock and aborts,breaking the deadlock. The clock-valued time stamps also ensure that nofalse deadlocks are detected, without additional protocol to eliminateobsolete tokens. Arguments for the correctness of the protocol aredeveloped