2026-07-22T14:19:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6334 2024-03-06T10:37:44Z ddc:004 open_access

A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems Marasevic, Jelena Stein, Clifford Zussman, Gil Fairness distributed and stateless algorithms resource allocation We study weighted alpha-fair packing problems, that is, the problems of maximizing the objective functions (i) sum_j w_j*x_j^{1-alpha}/(1-alpha) when alpha > 0, alpha != 1 and (ii) sum_j w_j*ln(x_j) when alpha = 1, over linear constraints A*x <=b, x >= 0, where wj 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 epsilon-approximate solution in time (number of distributed iterations) that has an inverse polynomial dependence on the approximation parameter epsilon 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 alpha -> 0, alpha -> 1, and alpha -> infinity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jelena Marasevic and Clifford Stein and Gil Zussman 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.54 urn:nbn:de:0030-drops-63344 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.54 eng https://creativecommons.org/licenses/by/3.0/legalcode