Parallel cycle detection in distributed databases

摘要

A deadlock detection algorithm is presented, by which each node in a network can decide locally whether a deadlock exists. Besides the problem of deadlock detection, we also take into account the problem of cycle detection in graphs distributed over several nodes. This problem arises in several locking protocols like the RAC-locking protocol in a distributed environment. The proposed algorithm is based on the idea of sending relevant paths of the wait-for graph by broadcast messages to each other node requiring only one physical transmission. In order to detect deadlocks only locally each node collects all paths sent in a local graph. As this graph has to be equal within all nodes a protocol has been developed which is responsible for ensuring equality. Finally, we determine the overhead caused by this protocol within the network. Besides, we also propose a broadcast two-phase commit protocol exploiting the facility of a broadcast message.