A Fast Distributed Algorithm for α-Fair Packing Problems.
Jelena Marašević, Clifford Stein, Gil Zussman · arXiv (Cornell University) · 2015
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 paper, we study weighted �-fair packing problems, that is, the problems of maximizing the objective functions P j wjx 1 � j /(1 − �) when � 6 1 and P j wj lnxj when � = 1 over linear constraints Ax ≤ 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 �. The algorithm uses simple local update rules and is stateless (namely, it allows asynchronous updates, is self-stabilizing, and allows incremental and local adjustments). It converges to approximate solutions in running times that have an inverse polynomial dependence on the approximation parameter . The convergence time has polylogarithmic dependence on the problem size for � 6 1, and a nearly-linear dependence on the number of variables for � = 1. These are the best convergence times known for these problems.