Abstract
Resource Allocation on Dynamic Conflict Graphs
by: Manhoi Choy and Ambuj K. Singh
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.
Keywords:
Distributed Algorithms, Dynamic Grpahs, Graph Coloring, ResourceAllocation.
Date:
July 1993
Document: 1993-11
