Technical Report CS0380

Title: Cooperative Distributed Algorithms for Dynamic Cycle Prevention
Authors: S. Katz and O. Shmueli
Abstract: Parallel distributed algorithms are presented for adding and deleting edges in a directed graph without creating a cycle. Such algorithms are useful for a variety of problems in distributed systems such as preventing deadlock or ordering priorities. The algorithms oprate in a realistic asynchronous instances of the algorithms. The distributed algorithms are derived from a sequential algorithm. In developing distributed versions of the algorithms form a sequential version, the vital role of an invariant is emphasized. Global correctness of the distributed algorithms relies on (locally) preseriving this invariant. Interacton and cooperation between verious activities 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 1985
To the main CS technical reports page

Computer science department, Technion