Browse Prior Art Database

Optimal Distributed Resource Allocation

IP.com Disclosure Number: IPCOM000128220D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 17 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

John Reif: AUTHOR [+4]

Abstract

In this paper we consider a resource allocation problem in a distributed network, where processors' speeds can vary dynamically. The problem is local in the sense that the maximum number of users competing for a particular resource at any time instant is upper bounded by a constant v and also at any time instant the maximum number of resources that a user is willing to get is upper bounded by a constant k. Each user's demands for resources may change dynamically. Our solutions to - the problem are real time since our algorithm's response time is upper bounded by a function which does not depend on any global measure of the system of processes, and resources, except k and v. We improve here previous real time solutions given to the problem in [Reif, Spirakis, 1982B], which had response time of 0(vk). In this paper we provide probabilistic algorithms whose response time is polynanial to v and k. Our most efficient algorithm has response time 0(v-k). Unlike the probabilistic algorithms of (Reif, Spirakis, 1982B], we do not need to use random waits as means of avoidance of process starvation and of achieving probabilistic fairness. Instead, our algorithm employs a new method of probabilistic bidding, to resolve contention of users for resources. This technique is essential in achieving polynomial response time. We furthermore prove that our solution is optimal with respect to the average response to a user's re4uest. In particular we provide matching lower bounds f or any distributed algorithm, and these bounds are within a constant factor of the response time of our own algorithms. We also provide a suboptimal algorithm which is useful for improving the throughput rate of resource allocations in systems where the majority of users is willing to get only a few resources. This suboptimal algorithm does use random waits combined with probabilistic bidding. Our techniques employ limited parallelism within each process, together with the probabilistic bidding. (This limited parallelism is useful in achieving optimal response time, though we would still get polynanial response time without limited parallelism).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Optimal Distributed Resource Allocation

by

John Reif*

and

Paul Spirakis

Technical Report No. 62

0 March1983

This work was supported in part by the National Science Foundation Grant NSF-MCS79-21024, and the Office of Naval Research Contract NOOO 14-80-C-0647.

* Aiken Computation Laboratory, Harvard University.

Abstract

In this paper we consider a resource allocation problem in a distributed network, where processors' speeds can vary dynamically. The problem is local in the sense that the maximum number of users competing for a particular resource at any time instant is upper bounded by a constant v and also at any time instant the maximum number of resources that a user is willing to get is upper bounded by a constant k. Each user's demands for resources may change dynamically. Our solutions to - the problem are real time since our algorithm's response time is upper bounded by a function which does not depend on any global measure of the system of processes, and resources, except k and v.

We improve here previous real time solutions given to the problem in [Reif, Spirakis, 1982B], which had response time of 0(vk). In this paper we provide probabilistic algorithms whose response time is polynanial to v and k. Our most efficient algorithm has response time 0(v-k).

Unlike the probabilistic algorithms of (Reif, Spirakis, 1982B], we do not need to use random waits as means of avoidance of process starvation and of achieving probabilistic fairness. Instead, our algorithm employs a new method of probabilistic bidding, to resolve contention of users for resources. This technique is essential in achieving polynomial response time.

We furthermore prove that our solution is optimal with respect to the average response to a user's re4uest. In particular we provide matching lower bounds f or any distributed algorithm, and these bounds are within a constant factor of the response time of our own algorithms. We also provide a suboptimal algorithm which is useful for improving the throughput rate of resource allocations in systems where the majority of users is willing to get only a few resources. This suboptimal algorithm does use random waits combined with probabilistic bidding.

New York University Page 1 Dec 31, 1983

Page 2 of 17

Optimal Distributed Resource Allocation

Our techniques employ limited parallelism within each process, together with the probabilistic bidding. (This limited parallelism is useful in achieving optimal response time, though we would still get polynanial response time without limited parallelism).

1. Introduction

1.1 Resource Granting Systems

In this paper, we consider a resource allocation problem similar to that described in [Lynch, 198D] and [Reif, Spirakis, 1982B]. There are potentially an infinite number of processes in the system, and each has an integer name. Let the set of processes be called H . There is a potentially infinite set of resources, p,...