Marasevic, Jelena ;
Stein, Clifford ;
Zussman, Gil
A Fast Distributed Stateless Algorithm for alphaFair Packing Problems
Abstract
We study weighted alphafair packing problems, that is, the problems of maximizing the objective functions (i) sum_j w_j*x_j^{1alpha}/(1alpha) 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 nonnegative. 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 epsilonapproximate solution in time (number of distributed iterations) that has an inverse polynomial dependence on the approximation parameter epsilon and polylogarithmic dependence on the problem size. This is the first distributed algorithm for weighted alphafair packing with polylogarithmic convergence in the input size. The algorithm uses simple local update rules and is stateless (namely, it allows asynchronous updates, is selfstabilizing, and allows incremental and local adjustments). We also obtain a number of structural results that characterize alphafair allocations as the value of alpha is varied. These results deepen our understanding of fairness guarantees in alphafair packing allocations, and also provide insight into the behavior of alphafair allocations in the asymptotic cases alpha > 0, alpha > 1, and alpha > infinity.
BibTeX  Entry
@InProceedings{marasevic_et_al:LIPIcs:2016:6334,
author = {Jelena Marasevic and Clifford Stein and Gil Zussman},
title = {{A Fast Distributed Stateless Algorithm for alphaFair Packing Problems}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {54:154:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6334},
URN = {urn:nbn:de:0030drops63344},
doi = {10.4230/LIPIcs.ICALP.2016.54},
annote = {Keywords: Fairness, distributed and stateless algorithms, resource allocation}
}
23.08.2016
Keywords: 

Fairness, distributed and stateless algorithms, resource allocation 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 