Real Time Resource Allocation in a Distributed System.
Abstract
In this paper we consider a resource allocation problem which is local in the sense that the maximum number of users competing for a particular resource at any time instant is bounded and also at any time instant the maximum number of resources that a user is willing to get is bounded. The problem may be viewed as that of achieving matchings in dynamically changing hypergraphs, via a distributed algorithm. We show that this problem is related to the fundamental problem of handshake communication (which can be viewed as achieving matchings in a dynamically changing graph, 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 (that is, we give distributed algorithms with real time response). We make essential use of probabilistic techniques as first used by (Rabin, 80b), where processes are allowed to make independent probabilistion choices. On the other hand, no probability assumptions about the system behavior are made.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1982
- Accession Number
- ADA122557
Entities
People
- John Reif
- Paul Spirakis
Organizations
- Harvard University