| TR#: | CS0330 |
| Class: | CS |
| Title: | Cooperative Distributed Algorithms for Dynamic Cycle Prevention |
| Authors: | Shmuel Katz and Oded Shmueli |
| CS0330.pdf | |
| 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. |
| Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1984/CS/CS0330), 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