Document Open Access Logo

A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems

Authors Jelena Marasevic, Clifford Stein, Gil Zussman

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.54.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Jelena Marasevic
Clifford Stein
Gil Zussman

Cite As Get BibTex

Jelena Marasevic, Clifford Stein, and Gil Zussman. A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.54

Abstract

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.

Subject Classification

Keywords
  • Fairness
  • distributed and stateless algorithms
  • resource allocation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Zeyuan Allen-Zhu and Lorenzo Orecchia. Nearly-linear time positive LP solver with faster convergence rate. In Proc. ACM STOC'15, 2015. Google Scholar
  2. Zeyuan Allen-Zhu and Lorenzo Orecchia. A novel, simple interpretation of Nesterov’s accelerated method as a combination of gradient and mirror descent, Jan. 2015. arXiv preprint, URL: http://arxiv.org/abs/1407.1537.
  3. Zeyuan Allen-Zhu and Lorenzo Orecchia. Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel. In Proc. ACM-SIAM SODA'15, 2015. Google Scholar
  4. Anthony B Atkinson. On the measurement of inequality. J. Econ. Theory, 2(3):244-263, 1970. Google Scholar
  5. Baruch Awerbuch, Yossi Azar, and Rohit Khandekar. Fast load balancing via bounded best response. In Proc. ACM-SIAM SODA'08, 2008. Google Scholar
  6. Baruch Awerbuch and Rohit Khandekar. Greedy distributed optimization of multi-commodity flows. In Proc. ACM PODC'07, 2007. Google Scholar
  7. Baruch Awerbuch and Rohit Khandekar. Stateless distributed gradient descent for positive linear programs. SIAM J. Comput., 38(6):2468-2486, 2009. Google Scholar
  8. Yair Bartal, John Byers, and Danny Raz. Global optimization using local information with applications to flow control. In Proc. IEEE FOCS'97, 1997. Google Scholar
  9. Amir Beck, Angelia Nedić, Asuman Ozdaglar, and Marc Teboulle. An O(1/k) gradient method for network resource allocation problems. IEEE Trans. Control Netw. Syst., 1(1):64-73, 2014. Google Scholar
  10. Dimitri Bertsekas and Robert Gallager. Data Networks. Prentice Hall, 1992. Google Scholar
  11. Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. On the efficiency-fairness trade-off. Manag. Sci, 58(12):2234-2250, 2012. Google Scholar
  12. Thomas Bonald and James Roberts. Multi-resource fairness: Objectives, algorithms and performance. In Proc. ACM SIGMETRICS'15, 2015. Google Scholar
  13. Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2009. Google Scholar
  14. Anna Charny, David D Clark, and Raj Jain. Congestion control with explicit rate indication. In Proc. IEEE ICC'95, 1995. Google Scholar
  15. Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. Tatonnement beyond gross substitutes?: Gradient descent to the rescue. In Proc. ACM STOC'13, 2013. Google Scholar
  16. Shlomi Dolev. Self-stabilization. MIT press, 2000. Google Scholar
  17. Lisa Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math., 13(4):505-520, 2000. Google Scholar
  18. Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 37(2):630-652, 2007. Google Scholar
  19. Naveen Garg and Neal Young. On-line end-to-end congestion control. In Proc. IEEE FOCS'02, 2002. Google Scholar
  20. Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proc. USENIX NSDI'11, 2011. Google Scholar
  21. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. In Proc. ACM STOC'14, 2014. Google Scholar
  22. Jeffrey Jaffe. Bottleneck flow control. IEEE Trans. Commun., 29(7):954-962, 1981. Google Scholar
  23. Kamal Jain and Vijay Vazirani. Eisenberg-gale markets: Algorithms and structural properties. In Proc. ACM STOC'07, 2007. Google Scholar
  24. Carlee Joe-Wong, Soumya Sen, Tian Lan, and Mung Chiang. Multiresource allocation: Fairness-efficiency tradeoffs in a unifying framework. IEEE/ACM Trans. Netw., 21(6):1785-1798, 2013. Google Scholar
  25. Frank Kelly, Aman Maulloo, and David Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soc., 49(3):237-252, 1998. Google Scholar
  26. Frank Kelly and Elena Yudovina. Stochastic networks, volume 2. Cambridge University Press, 2014. Google Scholar
  27. Jon Kleinberg, Yuval Rabani, and Éva Tardos. Fairness in routing and load balancing. In Proc. IEEE FOCS'99, 1999. Google Scholar
  28. Christos Koufogiannakis and Neal Young. Beating simplex for fractional packing and covering linear programs. In Proc. IEEE FOCS'07, 2007. Google Scholar
  29. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In Proc. ACM-SIAM SODA'06, 2006. Google Scholar
  30. Amit Kumar and Jon Kleinberg. Fairness measures for resource allocation. In Proc. IEEE FOCS'00, 2000. Google Scholar
  31. Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness in network resource allocation. In Proc. IEEE INFOCOM'10, 2010. Google Scholar
  32. Steven Low, Fernando Paganini, and John Doyle. Internet congestion control. IEEE Control Systems, 22(1):28-43, 2002. Google Scholar
  33. Michael Luby and Noam Nisan. A parallel approximation algorithm for positive linear programming. In Proc. ACM STOC'93, 1993. Google Scholar
  34. Jelena Marašević, Clifford Stein, and Gil Zussman. Max-min fair rate allocation and routing in energy harvesting networks: Algorithmic analysis. In Proc. ACM MobiHoc'14, 2014. Google Scholar
  35. Jelena Marašević, Cliff Stein, and Gil Zussman. A fast distributed stateless algorithm for α-fair packing problems, Feb. 2016. arXiv preprint, URL: http://arxiv.org/abs/1502.03372v3.
  36. Bill McCormick, Frank Kelly, Patrice Plante, Paul Gunning, and Peter Ashwood-Smith. Real time alpha-fairness based traffic engineering. In Proc. ACM HotSDN'14, 2014. Google Scholar
  37. Nimrod Megiddo. Optimal flows in networks with multiple sources and sinks. Math. Program., 7(1):97-107, 1974. Google Scholar
  38. Jeonghoon Mo and Jean Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Trans. Netw., 8(5):556-567, October 2000. Google Scholar
  39. Damon Mosk-Aoyama, Tim Roughgarden, and Devavrat Shah. Fully distributed algorithms for convex optimization problems. In Proc. DISC'07, 2007. Google Scholar
  40. Yurii Nesterov. Introductory lectures on convex optimization, volume 87. Springer Science &Business Media, 2004. Google Scholar
  41. Christos Papadimitriou and Mihalis Yannakakis. Linear programming without the matrix. In Proc. ACM STOC'93, 1993. Google Scholar
  42. Serge Plotkin, David Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res., 20(2):257-301, 1995. Google Scholar
  43. Božidar Radunović and Jean-Yves Le Boudec. A unified framework for max-min and min-max fairness with applications. IEEE/ACM Trans. Netw., 15(5):1073-1083, 2007. Google Scholar
  44. Saswati Sarkar and Leandros Tassiulas. Fair allocation of discrete bandwidth layers in multicast networks. In Proc. IEEE INFOCOM'00, 2000. Google Scholar
  45. Yung Yi and Mung Chiang. Stochastic network utility maximisation - a tribute to Kelly’s paper published in this journal a decade ago. Eur. Trans. Telecommun., 19(4):421-442, 2008. Google Scholar
  46. Neal Young. Sequential and parallel algorithms for mixed packing and covering. In Proc. IEEE FOCS'01, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact