Technical Report CS0604

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
PDFCS0604.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.)
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 (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

Computer science department, Technion
admin