Technical Report CS0330

Title: Cooperative Distributed Algorithms for Dynamic Cycle Prevention
Authors: Shmuel Katz and Oded Shmueli
Abstract: Parallel distributed algorithms are presented for adding and deleting arcs in a directed graph without creating a cycle. Such algorithms are useful for a variety of problems in distributed systems such as deadlock prevention. The algorithms operate in a realistic asynchronous computer network environment. In this environment there are numerous possible interactions between instances of the algorithm at various nodes:

The distributed algorithms are derived from a sequential algorithm. In developing the distributed version of the algorithm from a sequential version, the vital role of an invariant is emphasized. Global correctness of the distributed algorithms relies on (locally) preserving this invariant. Interactions and cooperatlon between various activations of the algorithms are exploited in order to minimize redundant computation.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1984
To the main CS technical reports page

Computer science department, Technion