Rigorous Systems Research Group (RSRG) Seminar

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 α-fair allocations. 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 w_j x_j^{1- α} /(1- α) when α ≠ 1 and Σ_j w_j ln(x_j) when α = 1 over linear constraints Ax ≤ b, x ≥ 0, where w_j are positive weights and A and b are non-negative. The algorithm uses simple local update rules, 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 ɛ and poly-logarithmic dependence on the problem size. These are the best convergence times known for these problems. Time-permitting, I will also talk about our structural results that characterize the behavior of α-fair allocations in the asymptotic cases when α tends to zero, one, or infinity. 

The talk is based on a recent joint work with Cliff Stein and Gil Zussman.