Accession Number:

ADA114856

Title:

Real Time Resource Allocation in a Distributed System.

Descriptive Note:

Technical rept.,

Corporate Author:

HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s):

• Reif,John
• Spirakis,Paul

Report Date:

1982-02-01

Pagination or Media Count:

28.0

Abstract:

A resource allocation problem is considered which is local in the sense that the number of users competing for a particular resource at any time instant is bounded and also at any time instant the number of resources that a user is willing to get is bounded. The problem may be viewed as distributedly achieving matchings in dynamically changing hypergraphs. We show that this problem is related to the fundamental problem of handshake communication this problem can be viewed as achieving matchings in dynamically changing graphs, via distributed algorithms in that an efficient solution to each of them implies an efficient solution to the other. We provide real-time solutions to the resource allocation problem i.e., distributed algorithms with real time response via probabilistic techniques. No probability assumptions about the system behavior are made, but processes are allowed the ability to make independent probabilistic choices. One of our solutions assumes the existence of an underlying efficient handshake communication system. Another is based on basic synchronization primitives flag variables. The special case of equi-speed processes is examined. Applications are drawn to dining philosophers, scheduling and two-phase locking in databases.

Descriptors:

• *Resource management
• Allocations
• Data bases
• Real time
• Algorithms
• Scheduling
• Probability
• Distribution
• Probability distribution functions

Subject Categories:

• Administration and Management
• Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE