A Caltech Library Service

Optimal Distributed Resource Allocation

Ginis, Roman (1999) Optimal Distributed Resource Allocation. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] Postscript - Submitted Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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)
Additional Information:© 1999 California Institute of Technology. Submitted June 11, 1999.
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1999.cs-tr-99-08
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26850
Deposited By: Imported from CaltechCSTR
Deposited On:30 Apr 2001
Last Modified:03 Oct 2019 03:18

Repository Staff Only: item control page