Precomputed Dominant Resource Fairness
Serdar Metin · 2025
Read Precomputed Dominant Resource Fairness by Serdar Metin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08846.txt.
Introduction
Serdar Metin looks again at Dominant Resource Fairness, the widely used scheme to share many resource types fairly in clouds and data centers. Fair shares were long studied for one resource type. Dominant Resource Fairness spread max-min fairness to mixed demands across several resources. It has prized traits such as sharing incentive, envy-freeness, Pareto efficiency, and strategy-proofness.
Metin studies the structure of the first method with care. He proposes a new form, Precomputed Dominant Resource Fairness, named for its main work rule. The new method comes close to the first method's shares in fewer steps. Faster shares matter where schedulers must split compute power, memory, and other resources among many users all the time. The paper refines a core cloud method in theory.
Catalog record
| CREATOR | Serdar Metin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08846
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Precomputed Dominant Resource Fairness Serdar Metin Abstract Although resource allocation is a well studied problem in computer science, until the prevalence of distributed systems, such as computing clouds and data centres, the question had been addressed predominantly for single resource type scenarios. At the beginning of the last decade, with the introuction of Dominant Resource Fairness, the studies of the resource allocation problem has finally extended to the multiple resource type scenarios. Dominant Resource Fairness is a solution, addressing the problem of fair allocation of multiple resource types, among users with heterogeneous demands. Based on Max-min Fairness, which is a well established algorithm in the literature for allocating resources in the single resource type scenarios, Dominant Resource Fairness generalises the scheme to the multiple resource case. It has a number of desirable properties that makes it preferable over alternatives, such as Sharing Incentive, Envy-Freeness, Pareto Efficiency, and Strategy Proofness, and as such, it is widely adopted in distributed systems. In the present study, we revisit the original study, and analyse the structure of the algorithm in closer view, to come up with an alternative algorithm, which approximates the Dominant Resource Fairness allocation in fewer steps. We name the new algorithm Precomputed Dominant Resource Fairness, after its main working principle. Keywords Resource Distribution \cdot Dominant Resource Fairness \cdot Precomputed 1 Introduction Dominant Resource Fairness (DRF) is a resource allocation scheme, which aims to provide fairness of allocation among users with heterogeneous demands, in a time-sharing system with multiple resource types, such as computing clouds ( Ghodsi et al. 2011 ) . The services offered by these systems may include processing power, memory, and bandwidth, all of which are expected to be distributed fairly among the clients, according to some definition of fairness. Although the problem has been well-studied for single resource types ( Keshav 1997 ; Bertsekas et al. 1992 ) , prior to DRF, less attention was paid to the multi-resource scenarios. The general approach was to adopt well established solutions for single resource allocation, such as Max-min Fairness (MF) and its derivatives, for a fixed bundle with differing amounts of resources from each resource type; e.g. standardised virtual machines. But this approach leads to inefficiencies, since the needs of different users are heterogeneous, where one needs predominantly one resource type, the other needs another. In the end, users ended up with unused resources that come in the bundle with the resources they need, where at the same time there were other users in the system in demand of those unused resources. Built on the MF premise, which aims to maximise the minimum share given to any user in a single resource setting, DRF aims to generalise the scheme by maximising the minimum relative share given to any user, over her dominant share; which in turn is defined for each user as the highest ratio of her demanded resources to their total reserve in the system (e.g. the ratio of demanded memory to the total available memory). The rest of the resources is allocated, for each user, in their fixed proportions to the user’s dominant share, which is known as the Leontief Preferences in the economy literature. DRF has acquired wide adoption in the distributed systems and cluster computation because of its properties, such as being Pareto optimal , Envy Free , Strategy Proof , and creating Sharing Incentive . In the present paper, we analyse the DRF algorithm as introduced by Ghodsi et al. 2011 in closer view, and based on the observations gathered thereby, introduce a new algorithm to approximate the DRF allocation in fewer steps. We call this new algorithm Precomputed Dominant Resource Fairness (PDRF), after its main working principle of precomputing the main allocation loop of DRF, and assigning resources to users without going through the tedious iterations of the loop. One study that also needs to be mentioned at the onset, is that of Parkes et al. 2015 , the method and the findings of which closely resemble to that of the present study, with some key differences that allow us to implement our newly proposed algorithm. The analysis method and the algorithm they propose, the Extended Dominant Resource Fairness (EDRF) are similarly based on precomputing the final allocation of DRF, but they modeled the underlying linear programming problem, rather than the algorithm itself. They construct a theoretical framework that allows them to provide more rigorous proofs of DRF properties, which is the main objective of the article. We elaborate on this in Section 3.2 . The rest of this paper is organised as follows: In the next section, we briefly review the literature for related work. In Section 3.4 , we present our model, after reviewing DRF and EDRF in subsections 3.1 and 3.2 , respectively, and introducing an analysis method in subsection 3.3 . In section 4 , we present the results of the tests we carried out with PDRF. In Section 5 we analyse PDRF performance. Section 6 consists of three subsections, in which we discuss higher order cycles in PDRF ( 6.1 ), Pareto Efficiency property ( 6.2 ), and weighting policies ( 6.3 ), which we believe, are important points to focus on critically. Finally, we conclude in Section 7 . 2 Related Work DRF is first proposed by Ghodsi et al. 2011 , where they introduce the new notion of establishing an MF allocation among dominant shares , rather than a fixed resource bundle of different resource types. They also provide an algorithm to carry out the distribution, and produce empirical data to demonstrate the performance of the algorithm. In their theoretical sections, they compare the virtues of the newly introduced allocation scheme to the ones existing in the economy literature, for this is as much a problem in the field of economy as it is in the field of computer science. Their results clearly demonstrate that DRF possesses various advantages over its alternatives. The model is challenged by Dolev et al. 2012 . They developed an alternative fairness notion, which they refer to as no justified complaints , based on the assumption that the fairness of distribution of resources should be assessed from a global system point of view, considering the bottleneck property of resources. A resource is a bottleneck resource, if the availability of this resource is limited and there is a race condition for accessing it. They developed the Bottleneck Based Fairness (BBF) algorithm to implement this paradigm as an alternative to DRF, with relative advantages of each algorithm in different use cases. Not only challenged, but DRF has also been adopted, generalised, contextualised, or extended to different cases. For example, Gutman and Nisan 2012 , introduced an economical framework to compare and contrast the two systems described above. While doing so they also critically assessed both approaches from an economic point of view. Joe-Wong et al. 2013 investigates the trade-off between fairness and efficiency, providing a unifying framework with two families of fairness functions, DRF being a special case in one of them. Kash et al. 2014 takes a scenario in which the complete information on demands is not available, since users arrive and leave the system, and develops a Dynamic DRF (DDRF) to address