| TR#: | CS0604 |
| Class: | CS |
| Title: | HOW TO KEEP B A DYNAMIC DISTRIBUTIVE DIRECTED GRAPH ACYCLIC A AND YET GRANT ALL REQUESTS OF EDGE ADDITIONS |
| Authors: | Shimon Even and Yachin Pnueli |
| CS0604.pdf | |
| Abstract: | The problem of cycle prevention in dynamic distributive networks arises in many distributive applications such as distributive databases and operating systems. A typical application is a deadlock prevention algorithm (in which every edge indicates some dependence relation and a cycle indicates a deadlock). Let G (V .E) be a finite directed graph where every node in V is a distinct processor. The problem is to perform, on-line, a series of given requests to add or delete edges in the graph while keeping it acyclic. Since, for a given set E. some edge additions may be performed only after some other edges are removed from the graph, the problem can be restated as follows: Given such a series of requests, delay each request in such a way that every request'is eventually granted while keeping the graph acyclic. We present an algorithm which solves this problem. Katz and Shmueli [KS] treated the same problem. Our solution differs in that it has the following property. If every request to add an edge k -+ j. is such that there is no path from j to k which persists forever, then every request to add an edge is eventually granted. The message complexity of the algorithm is 0 (IE I.IV I) messages per request. (Requests to delete an edge are performed immediately without sending any messages.) |
| 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/1990/CS/CS0604), 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 1990
To the main CS technical reports page