Abstract
Knot detection in a distributed graph is an important problem and finds applications in deadlock detection in several areas such as store-and-forward networks, distributed simulation, and distributed database systems. This paper presents an efficient distributed algorithm to detect if a node is part of a knot in a distributed graph. The algorithm requires 2e. messages and a delay of 2(d +1) message hops to detect if a node in a distributed graph is in a knot (here, e is the number of edges in the reachable part of the distributed graph and d Is its diameter). A significant advantage of this algorithm is that it not only detects if a node is involved in a knot, but also finds exactly which nodes are Involved in the knot. Moreover, if the node is not involved in a knot, but is only involved in a cycle, then it finds the nodes that are in a cycle with that node. We illustrate the working of the algorithm with examples. The paper ends with a discussion on how the information about the nodes involved in the knot can be used for deadlock resolution and also on the performance of the algorithm.
Original language | English |
---|---|
Pages (from-to) | 961-972 |
Number of pages | 12 |
Journal | IEEE Transactions on Parallel and Distributed Systems |
Volume | 14 |
Issue number | 10 |
DOIs | |
State | Published - Oct 2003 |
Bibliographical note
Funding Information:The authors thank the anonymous referees and the associate editor for their detailed comments and valuable suggestions on an earlier version of the paper. The authors also thank Raphael Finkel for his comments on a preliminary version of this paper. A preliminary version of this paper appears in the IEEE Proceedings of the 31st International Conference on Parallel Processing [17]. This research was supported in part by the US National Science Foundation, CAREER Award # CCR-9983584.
Keywords
- Deadlock detection
- Distributed algorithms
- Distributed graph
- Distributed simulation
- Distributed systems
- Knot detection
ASJC Scopus subject areas
- Signal Processing
- Hardware and Architecture
- Computational Theory and Mathematics