A Distributed Algorithm for Resource Allocation with Probabilistic Quorum Systems

H. Yoshimura, K. Miura, and H. Kakugawa (Japan)


Distributed Algorithm, Coterie, Probabilistic Quorum Systems, Resource Allocation


The resource allocation problem is one of fundamental problems in distributed systems, and many resource models and resource allocation algorithms have been proposed in many literature. In this paper, we consider a problem of allocating a set of unnamed resources that can be overbooked. Such a resource model is suitable for sharing broadband communication channel by many nodes. We propose a randomized distributed resource allocation algorithm for such a resource model based on quorum scheme. Speci´Čücally, our algorithm uses probabilistic quorum system, which is an extension of coterie, and processes in a distributed system distributedly maintains status of resource allocation. We also show some experimental results on degree of overbooking of resources by computer simulations.

Important Links:

Go Back