A fast distributed stateless algorithm for -fair packing problems

DOI10.4230/LIPICS.ICALP.2016.54MaRDI QIDQ4598193zbMATH OpenOpenAlexFDO

Authors Jelena Marašević, Gil Zussman, Clifford Stein

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1502.03372

zbMATH Keywords

distributed and stateless algorithmsfairnessresource allocation

Mathematics Subject Classification ID

Distributed algorithms (68W15) Combinatorial optimization (90C27)

Abstract: Over the past two decades, fair resource allocation problems have received considerable attention in a variety of application areas. However, little progress has been made in the design of distributed algorithms with convergence guarantees for general and commonly used $alpha$-fair allocations. In this paper, we study weighted $alpha$-fair packing problems, that is, the problems of maximizing the objective functions (i) $su{m}_j{w}_j{x}_j^{1-alpha}/(1-alpha)$ when $alpha>0$, $alphaeq1$ and (ii) $su{m}_j{w}_{j}ln{x}_j$ when $alpha=1$, over linear constraints $Axleqb$, $xgeq0$, where $w_j$ are positive weights and $A$ and $b$ are non-negative. We consider the distributed computation model that was used for packing linear programs and network utility maximization problems. Under this model, we provide a distributed algorithm for general $alpha$ that converges to an $varepsilon-$approximate solution in time (number of distributed iterations) that has an inverse polynomial dependence on the approximation parameter $varepsilon$ and poly-logarithmic dependence on the problem size. This is the first distributed algorithm for weighted $alpha-$fair packing with poly-logarithmic convergence in the input size. The algorithm uses simple local update rules and is stateless (namely, it allows asynchronous updates, is self-stabilizing, and allows incremental and local adjustments). We also obtain a number of structural results that characterize $alpha-$fair allocations as the value of $alpha$ is varied. These results deepen our understanding of fairness guarantees in $alpha-$fair packing allocations, and also provide insight into the behavior of $alpha-$fair allocations in the asymptotic cases $alphaightarrow0$, $alphaightarrow1$, and $alphaightarrowinfty$.

Recommendations

• Fair packing and covering on a relative scale
• The price of fairness
• Pricing for fairness: distributed resource allocation for multiple objectives
• Pricing for fairness
• Stateless distributed gradient descent for positive linear programs

Cited in

(2)

• Stateless distributed gradient descent for positive linear programs
• Fair packing and covering on a relative scale

This page was built for publication: A fast distributed stateless algorithm for \(\alpha\)-fair packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598193)