Title: A stabilising optimal k-out-of-ℓ resources allocation algorithm

Authors: Rachid Hadid

Addresses: MIS, Université de Picardie Jules Verne, CS 52501 80025 Cedex, Chemin du Thil, 80025 Amiens, France

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.

Keywords: resources allocation; k-out-of-ℓ resources allocation; k-out-of-ℓ exclusion; ℓ resources allocation; PIF scheme; distributed systems; fault-tolerance; self-stabilising.

DOI: 10.1504/IJKEDM.2018.094744

International Journal of Knowledge Engineering and Data Mining, 2018 Vol.5 No.3, pp.173 - 194

Received: 27 May 2018
Accepted: 28 May 2018
Published online: 14 Sep 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article