Efficient distributed deadlock detection and resolution using probes, tokens, and barriers
Young Man Kim, Ten Hwang Lai, Neelam Soundarajan · 2002
Probes and tokens are used in many deadlock detection and resolution algorithms. A deadlock is detected by propagating probes along dependency edges. When the initiator p/sub i/ of a probe receives its probe back, it knows of the existence of a deadlock. p/sub i/ then sends out a token to clean up those probes in the deadlock; cycle which, if not removed, may later lead to phantom deadlock detections. Only after the token returns to p/sub i/ is the deadlock resolved by aborting a 'victim' (usually p/sub i/). As a result, all involved transactions remain waiting and all involved resources locked until the token returns to p/sub i/, although the deadlock was already detected when the probe returned to p/sub i/. This paper proposes the idea of barriers to allow the deadlock to be resolved without waiting for the token to return to p/sub i/, thereby reducing the average deadlock persistence time considerably.