Improved Bounds for Online Balanced Graph Re-Partitioning

Authors Rajmohan Rajaraman, Omer Wasim



PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.83.pdf
  • Filesize: 0.69 MB
  • 15 pages

Document Identifiers

Author Details

Rajmohan Rajaraman
  • Northeastern University, Boston, MA, USA
Omer Wasim
  • Northeastern University, Boston, MA, USA

Cite AsGet BibTex

Rajmohan Rajaraman and Omer Wasim. Improved Bounds for Online Balanced Graph Re-Partitioning. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.83

Abstract

We study the online balanced graph re-partitioning problem (OBGR) which was introduced by Avin, Bienkowski, Loukas, Pacut, and Schmid [Avin et al., 2020] and has recently received significant attention [Pacut et al., 2021; Henzinger et al., 2021; Henzinger et al., 2019; Tobias Forner et al., 2021; Bienkowski et al., 2021] owing to potential applications in large-scale, data-intensive distributed computing. In OBGR, we have a set of 𝓁 clusters, each with k vertices (representing processes or virtual machines), and an online sequence of communication requests, each represented by a pair of vertices. Any request (u,v) incurs unit communication cost if u and v are located in different clusters (and zero otherwise). Any vertex can be migrated from one cluster to another at a migration cost of α ≥ 1. We consider the objective of minimizing the total communication and migration cost in the competitive analysis framework. The only known algorithms (which run in exponential time) include an O(k²𝓁²) competitive [Avin et al., 2020] and an O(k𝓁 2^O(k)) competitive algorithm [Bienkowski et al., 2021]. A lower bound of Ω(k𝓁) is known [Pacut et al., 2021]. In an effort to bridge the gap, recent results have considered beyond worst case analyses including resource augmentation (with augmented cluster capacity [Avin et al., 2020; Henzinger et al., 2019; Henzinger et al., 2021]) and restricted request sequences (the learning model [Henzinger et al., 2019; Henzinger et al., 2021; Pacut et al., 2021]). In this paper, we give deterministic, polynomial-time algorithms for OBGR, which mildly exploit resource augmentation (i.e. augmented cluster capacity of (1+ε) k for arbitrary ε > 0). We improve beyond O(k²𝓁²)-competitiveness (for general 𝓁, k) by first giving a simple algorithm with competitive ratio O(k𝓁²log k). Our main result is an algorithm with a significantly improved competitive ratio of O(k𝓁 log k). At a high level, we achieve this by employing i) an ILP framework to guide the allocation of large components, ii) a simple "any fit" style assignment of small components and iii) a charging argument which allows us to bound the cost of migrations. Like previous work on OBGR, our algorithm and analysis are phase-based, where each phase solves an independent instance of the learning model. Finally, we give an Ω(α k𝓁 log k) lower bound on the total cost incurred by any algorithm for OBGR under the learning model, which quantifies the limitation of a phase-based approach.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online algorithms
  • graph partitioning
  • competitive analysis

Metrics

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

References

  1. Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2), April 2009. URL: https://doi.org/10.1145/1502793.1502794.
  2. Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, and Stefan Schmid. Dynamic balanced graph partitioning. SIAM Journal on Discrete Mathematics, 34(3):1791-1812, 2020. URL: https://doi.org/10.1137/17M1158513.
  3. Theophilus Benson, Aditya Akella, and David A. Maltz. Network traffic characteristics of data centers in the wild. In Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement, IMC '10, pages 267-280, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1879141.1879175.
  4. Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jiří Sgall, and Pavel Veselý. Improved analysis of online balanced clustering. In Approximation and Online Algorithms: 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6–10, 2021, Revised Selected Papers, pages 224-233, Berlin, Heidelberg, 2021. Springer-Verlag. URL: https://doi.org/10.1007/978-3-030-92702-8_14.
  5. Mosharaf Chowdhury, Matei Zaharia, Justin Ma, Michael I. Jordan, and Ion Stoica. Managing data transfers in computer clusters with orchestra. SIGCOMM Comput. Commun. Rev., 41(4):98-109, August 2011. URL: https://doi.org/10.1145/2043164.2018448.
  6. Guy Even, Joseph (Seffi) Naor, Satish Rao, and Baruch Schieber. Fast approximate graph partitioning algorithms. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '97, pages 639-648, USA, 1997. Society for Industrial and Applied Mathematics. Google Scholar
  7. Guy Even, Joseph Seffi Naor, Satish Rao, and Baruch Schieber. Divide-and-conquer approximation algorithms via spreading metrics. J. ACM, 47(4):585-616, July 2000. URL: https://doi.org/10.1145/347476.347478.
  8. Uriel Feige and Robert Krauthgamer. A polylogarithmic approximation of the minimum bisection. SIAM Rev., 48(1):99-130, January 2006. URL: https://doi.org/10.1137/050640904.
  9. Uriel Feige, Robert Krauthgamer, and Kobbi Nissim. Approximating the minimum bisection size (extended abstract). In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, pages 530-536, New York, NY, USA, 2000. Association for Computing Machinery. URL: https://doi.org/10.1145/335305.335370.
  10. Tobias Forner, Harald Räcke, and Stefan Schmid. Online balanced repartitioning of dynamic communication patterns in polynomial time. In Symposium on Algorithmic Principles of Computer Systems (APOCS), pages 40-54, 2021. URL: https://doi.org/10.1137/1.9781611976489.4.
  11. M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified np-complete problems. In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC '74, pages 47-63, New York, NY, USA, 1974. Association for Computing Machinery. URL: https://doi.org/10.1145/800119.803884.
  12. Monika Henzinger, Stefan Neumann, Harald Räcke, and Stefan Schmid. Tight bounds for online graph partitioning. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2799-2818, USA, 2021. Society for Industrial and Applied Mathematics. Google Scholar
  13. Monika Henzinger, Stefan Neumann, and Stefan Schmid. Efficient distributed workload (re-)embedding. In Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '19, pages 43-44, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3309697.3331503.
  14. Robert Krauthgamer, Joseph (Seffi) Naor, and Roy Schwartz. Partitioning graphs into balanced components. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, pages 942-949, USA, 2009. Society for Industrial and Applied Mathematics. Google Scholar
  15. T. Leighton, F. Makedon, and S.G. Tragoudas. Approximation algorithms for vlsi partition problems. In IEEE International Symposium on Circuits and Systems, pages 2865-2868 vol.4, 1990. URL: https://doi.org/10.1109/ISCAS.1990.112608.
  16. Maciej Pacut, Mahmoud Parham, and Stefan Schmid. Optimal online balanced partitioning. In INFOCOM 2021, 2021. Google Scholar
  17. Cynthia A. Phillips, Cliff Stein, Eric Torng, and Joel Wein. Optimal time-critical scheduling via resource augmentation (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 140-149, New York, NY, USA, 1997. Association for Computing Machinery. URL: https://doi.org/10.1145/258533.258570.
  18. Arjun Roy, Hongyi Zeng, Jasmeet Bagga, George Porter, and Alex C. Snoeren. Inside the social network’s (datacenter) network. SIGCOMM Comput. Commun. Rev., 45(4):123-137, August 2015. URL: https://doi.org/10.1145/2829988.2787472.
  19. A. Schrijver. Theory of linear and integer programming. In Wiley-Interscience series in discrete mathematics and optimization, 1999. Google Scholar
  20. Horst D. Simon and Shang-Hua Teng. How good is recursive bisection? SIAM J. Sci. Comput., 18(5):1436-1445, September 1997. URL: https://doi.org/10.1137/S1064827593255135.
  21. Arjun Singh, Joon Ong, Amit Agarwal, Glen Anderson, Ashby Armistead, Roy Bannon, Seb Boving, Gaurav Desai, Bob Felderman, Paulie Germano, Anand Kanagala, Jeff Provost, Jason Simmons, Eiichi Tanda, Jim Wanderer, Urs Hölzle, Stephen Stuart, and Amin Vahdat. Jupiter rising: A decade of clos topologies and centralized control in google’s datacenter network. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, SIGCOMM '15, pages 183-197, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2785956.2787508.
  22. Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, February 1985. URL: https://doi.org/10.1145/2786.2793.
  23. Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227, 1977. URL: https://doi.org/10.1109/SFCS.1977.24.
  24. N. Young. Thek-server dual and loose competitiveness for paging. Algorithmica, 11(6):525-541, June 1994. URL: https://doi.org/10.1007/BF01189992.
  25. Neal E. Young. On-line file caching. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '98, pages 82-86, USA, 1998. Society for Industrial and Applied Mathematics. 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