A stabilising optimal k-out-of-ℓ resources allocation algorithm
by Rachid Hadid
International Journal of Knowledge Engineering and Data Mining (IJKEDM), Vol. 5, No. 3, 2018

Abstract: In distributed systems, resource allocation consists in managing fair access to a large number of processes to a typically small number of reusable resources. When the number of available resources is greater than one, the efficiency in concurrent accesses becomes an important issue, as a crucial goal is to minimise the waiting times to utilise these resources. In this paper, we present a k-out-of-ℓ resources allocation solution in tree networks. The k-out-of-ℓ resources allocation problem is a generalisation of the well-known ℓ resources allocation problem-there are ℓ units of the shared resource, any process can request up to k units (1 ≤ k ≤ ℓ) and no resource unit can be allocated to more than one process simultaneously. The proposed solution is optimal in terms of waiting times of processes to enter critical sections (get the requested units of the shared resource), i.e., between two entries of a process to its critical section, no other process can enter its critical section more than once after stabilisation. Furthermore, every process's request is granted in at most O(n × h) rounds. Since our algorithm is stabilising, it does not require initialisation and withstands transient faults. The stabilisation time of the algorithm is 3 × h + 6 rounds and the waiting time is (n − 1), where h and n are the height and the size (number of processes) of the tree, respectively. In addition, this algorithm satisfies all the requirements of the k-out-of-ℓ resources allocation problem: safety, fairness and (k,ℓ)-liveness.

Online publication date: Fri, 14-Sep-2018

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Knowledge Engineering and Data Mining (IJKEDM):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com