Real Time Resource Allocation in a Distributed System.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1982
- Accession Number
- ADA114856
Entities
People
- John Reif
- Paul Spirakis
Organizations
- Harvard University