Towards Distributed Lexicographically Fair Resource Allocation with an Indivisible Constraint

Chuanyou Li, Tianwei Wan, Junmei Han and Wei Jiang
Additional contact information
Chuanyou Li: School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
Tianwei Wan: School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
Junmei Han: National Key Laboratory for Complex Systems Simulation, Department of Systems General Design, Institute of Systems Engineering, AMS, Beijing 100083, China
Wei Jiang: National Key Laboratory for Complex Systems Simulation, Department of Systems General Design, Institute of Systems Engineering, AMS, Beijing 100083, China

Mathematics, 2022, vol. 10, issue 3, 1-23

Abstract: In the cloud computing and big data era, data analysis jobs are usually executed over geo-distributed data centers to make use of data locality. When there are not enough resources to fully meet the demands of all the jobs, allocating resources fairly becomes critical. Meanwhile, it is worth noting that in many practical scenarios, resources waiting to be allocated are not infinitely divisible. In this paper, we focus on fair resource allocation for distributed job execution over multiple sites, where resources allocated each time have a minimum requirement. Aiming at the problem, we propose a novel scheme named Distributed Lexicographical Fairness ( DLF ) targeting to well specify the meaning of fairness in the new scenario considered. To well study DLF , we follow a common research approach that first analyzes its economic properties and then proposes algorithms to output concrete DLF allocations. In our study, we leverage a creative idea that transforms DLF equivalently to a special max flow problem in the integral field. The transformation facilitates our study in that by generalizing basic properties of DLF from the view of network flow, we prove that DLF satisfies Pareto efficiency, envy-freeness, strategy-proofness, relaxed sharing incentive and 1 2 -maximin share. After that, we propose two algorithms. One is a basic algorithm that stimulates a water-filling process. However, our analysis shows that the time complexity is not strongly polynomial. Aiming at such inefficiency, we then propose a new iterative algorithm that comprehensively leverages parametric flow and push-relabel maximal flow techniques. By analyzing the steps of the iterative algorithm, we show that the time complexity is strongly polynomial.

Keywords: distributed settings; fair resource allocation; network flow; indivisibility (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/3/324/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/3/324/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:3:p:324-:d:729640

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().