An Efficient Distributed Algorithm for Detection of Knots and Cycles in a Distributed Graph

D. Manivannan, Mukesh Singhal

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

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 languageEnglish
Pages (from-to)961-972
Number of pages12
JournalIEEE Transactions on Parallel and Distributed Systems
Volume14
Issue number10
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'An Efficient Distributed Algorithm for Detection of Knots and Cycles in a Distributed Graph'. Together they form a unique fingerprint.

Cite this