A distributed algorithm for the detection of local cycles and knots

The purpose of this paper is to present an efficient distributed cycle/knot detection, algorithm for general graphs which will determine whether a given node is a member of a knot or a cycle. This is relevant to an application such as parallel simulation in which (1) cycles and knots can arise frequently, (2) the size of the graph is very large and (3) it is necessary to know if a given node is in a cycle or a knot. The algorithm is based on a diffusing computation. It requires less communication cost than preceding algorithms and is the first algorithm capable of detecting both cycles and knots. The algorithm differs from the classical diffusing computation methods through its use of incomplete search messages to speed up the computation. The algorithm requires a total of at most 2m messages, where m is the number of links. This is compared to Chandy-Misra´s algorithm (1982) which requires at least (3m+n), where n is a number of nodes and m is the number of links. The algorithm. Requires O(log(n)) bits of memory. Various applications for the cycle/knot detection algorithm are presented. In particular, we demonstrate its importance to deadlock detection to algorithms for parallel simulation which employ a blocking paradigm and a deadlock breaking technique known as TNE/DLTNE