Skip to main content

Real time resource allocation in distributed systems

Publication ,  Conference
Reif, J; Spirakis, P
Published in: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
August 18, 1982

In this paper we consider a resource allocation problem which is local in the sense that the maxim~a 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 realtime 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 probabilistic choices. On the other hand, no probability assumptions about the system behavior are made. One of our solutions assumes the existence of an underlying real-time handshake communication system, as described in [Reif, Spirakis, 81]. Our other solution is based on efficient synchronization by flag variables, which are written only by one process and read by at most one other process. The special case of equi-speed processes is first examined. Then we generalize to asynchronous processes. Applications are made to dining philosophers, scheduling and two-phase locking in databases.

Duke Scholars

Published In

Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

DOI

ISBN

0897910818

Publication Date

August 18, 1982

Start / End Page

84 / 94
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J., & Spirakis, P. (1982). Real time resource allocation in distributed systems. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (pp. 84–94). https://doi.org/10.1145/800220.806685
Reif, J., and P. Spirakis. “Real time resource allocation in distributed systems.” In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 84–94, 1982. https://doi.org/10.1145/800220.806685.
Reif J, Spirakis P. Real time resource allocation in distributed systems. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 1982. p. 84–94.
Reif, J., and P. Spirakis. “Real time resource allocation in distributed systems.” Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 1982, pp. 84–94. Scopus, doi:10.1145/800220.806685.
Reif J, Spirakis P. Real time resource allocation in distributed systems. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 1982. p. 84–94.

Published In

Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

DOI

ISBN

0897910818

Publication Date

August 18, 1982

Start / End Page

84 / 94