Resource Allocation on Dynamic Conflict Graphs

Report ID: 
1993-11
Authors: 
Manhoi Choy and Ambuj K. Singh
Date: 
1993-07-01 05:00:00

Abstract

The sharing of resources among processes in a distributed system leads to aconflict graph that may change with time. Resource allocation over a staticconflict graph (also called the dining philosophers problem) has been studiedextensively. We seek to solve resource allocation on dynamic conflict graphsby using existing algorithms that work only for static conflict graphs. In theprocess we define the notion of a snapshot of a dynamic graph, specify itsproperties, and show how it can be combined with static graph algorithms toyield efficient solutions for dynamic graphs.

Document

File 1993-11.ps