Ginis, Roman (1999) Optimal Distributed Resource Allocation. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1999.cs-tr-99-08
See Usage Policy.
Other (Adobe PDF (1.75MB))
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1999.cs-tr-99-08
We present and explore the problem of automatic distributed resource allocation for a large scale system operating on the basic principles of a free market economy. We model such environment as a resource allocation problem where the producers and consumers are numerous distributed entities controlled by different interests that trade resource time to achieve their goals and maximize their individual objective functions. A consumer specifies her problem in terms of a graph of resource types that describes temporal relationships between the resources. A resource type is expressed by a predicate that establishes the necessary properties that a resource needs to satisfy to be used in a solution. The consumer also specifies an objective function in terms of the resource type attributes, that needs to be maximized while searching for a solution. A feasible reservation on the part of a consumer, is a set of resources each of which satisfies the required constraints of its type and is available at such times as dictated by the temporal execution order specified by the graph. We present two polynomial-time algorithms for finding feasible and optimal reservation plans. We also introduce a method to perform a distributed atomic transaction to commence the reservation of the chosen resources. The transaction method is based oil the call-option financial instrument that is well suited for the problem. Finally we show how to use these algorithms to solve the problems in crisis management applications.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Computer Science Technical Reports|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechCSTR|
|Deposited On:||30 Apr 2001|
|Last Modified:||26 Dec 2012 14:07|
Repository Staff Only: item control page