Browse Prior Art Database

Using Hashing to Reduce Communication in Distributed Deadlock Detection Algorithms

IP.com Disclosure Number: IPCOM000099631D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 112K

Publishing Venue

IBM

Related People

Stamos, JW: AUTHOR

Abstract

A mechanism is disclosed for decreasing the amount of communication required to do deadlock detection in a multi-machine environment that supports the AND model of resource requests.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Using Hashing to Reduce Communication in Distributed Deadlock Detection Algorithms

       A mechanism is disclosed for decreasing the amount of
communication required to do deadlock detection in a multi-machine
environment that supports the AND model of resource requests.

      The disclosed mechanism has two sets of tasks: "redistribution
tasks" that redistribute wait-for information, and "detection tasks"
that use the redistributed wait-for information to detect deadlocks.
In steady-state situations there need not be any synchronization
between the detection of deadlocks and the redistribution of wait-for
information, and both sets of tasks can execute simultaneously.

      A redistribution task runs on every machine that has resources.
 All the redistribution tasks use the same hashing function to map
each transaction executed by the system to a coordinator machine.
When transaction T waits for transaction U on machine M, M's
redistribution task sends this wait-for information to the detection
task on the coordinator for transaction T, say, machine N.  (M and N
may be the same machine or different machines.)  M need not send the
wait-for information immediately.  When transaction T is no longer
waiting for transaction U on machine M, M's redistribution task sends
this change to the detection task on machine N.  Again, M need not
send the change immediately.

      A detection task runs on every machine that the hashing
function has designated as a coordinator.  Each detection task
processes the messages sent by redistribution tasks and maintains the
wait-for information for all transactions that hash to that
coordinator.  In addition, the detection tasks together execute a
distributed deadlock detection protocol that exploits the fact that a
copy of all wait-for information for a given transaction is kept at
the coordinator for that transaction.  Such a protocol may be based
on an existing distributed deadlock detection protocol, such as
described in (1) or (2).  The necessary changes to these protocols
are described below.

      When an existing distributed deadlock detection protocol pushes
a path or chases an edge, it sends information to the set of machines
on which a given transaction may be waiting for another transaction.
This set may consist of one machine, several machines, or, in the
worst case, all the machines in the system.  Thus, the communication
is either unicast, multicast, or, in the worst case, broadcast.  When
hashing is used, as it is in the disclosed mechanism, the distributed
deadlock detection protocol can push a path or chase an edge by
sending information only to the unique coordinator fo...