A Fast Distributed Algorithm for α-Fair Packing Problems

Опубликовано 22 июня 2016, 0:17

Over the past two decades, fair resource allocation problems received considerable attention in a variety of application areas. While polynomial time distributed algorithms have been designed for max-min fair resource allocation, the design of distributed algorithms with convergence guarantees for the more general α-fair allocations received little attention. In this talk, I will present a fast distributed algorithm for weighted α -fair packing problems, that is, the problems of maximizing the objective functions Σj wj xj1- α /(1- α) when alpha ≠ 1 and Σj wj ln(xj) when alpha = 1 over linear constraints Ax ≤ b, x ≥ 0, where wj are positive weights and A and b are non-negative. The model of distributed computation is similar to the models used in previous work on packing linear programs and network utility maximization problems. The algorithm uses simple local update rules that mimic a tatonnement process, and is stateless (namely, it allows asynchronous updates, is self-stabilizing, and allows incremental and local adjustments). The algorithm converges to approximate solutions in running times that have an inverse polynomial dependence on the approximation parameter epsilon and poly-logarithmic dependence on the problem size. These are the best convergence times known for these problems. The talk is based on a recent joint work with Cliff Stein and Gil Zussman.