Paper Details

Implementing a Distributed Algorithm for Detection of Local Knots and Cycles in Directed Graphs

Authors: Souza, Geraldo Pereira de, Pfitscher, Gerson Henrique

Abstract:

In general, most deadlocks take form of cycles (in database systems) and knots (in communication systems). Boukerche and Tropper have proposed a distributed algorithm to detect cycles and knots in generic graphs. Their algorithm has a message complexity of 2m vs. (at least) 4m for the Chandy and Misra algorithm, where m is the number of links in the graph, and requires O (n log n) bits of memory, where n is the number of nodes. We have implemented Boukerche's algorithm. Our implementation of the algorithm is based on the construction of processes of the CSP model. The implementation was done using JCSP, an implementation of CSP for Java.

Proceedings:

Communicating Process Architectures 2002, James S. Pascoe, Roger J. Loader, Vaidy S. Sunderam, 2002, pp 371 - 386 published by IOS Press, Amsterdam

Files: PDF, PS

This record in other formats:

Web page: BibTEX, Refer
Plain text: BibTEX, Refer

If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.