A DISTRIBUTED GRAPH ALGORITHM FOR THE DETECTION OF LOCAL CYCLES AND KNOTS

In this paper, a distributed cycle/knot detection algorithm for genera l graphs is presented. The algorithm distinguishes between cycles and knots and is the first algorithm to our knowledge which does so. It is especially relevant to an application such as parallel simulation in which 1) cycles and knots can arise frequently, 2) the size of the gra ph is very large, and 3) it is necessary to know if a given node is in a cycle or a knot. It requires less communication than previous algor ithms-2m vs. (at least) (4m) for the Chandy and Misra algorithm, where m is the number of links in the graph. It requires O (nlog (n)) bits of memory, where n is the number of nodes. The algorithm differs from the classical diffusing computation methods through its use of incompl ete search messages to speed up the computation. We introduce a markin g scheme in order to identify strongly connected subcomponents of the graph which cannot reach the initiator of the algorithm. This allows u s to distinguish between the case in which the initiator is in a cycle (only) or is in a knot.