本論文探討了在分散式系統中，如何通過不同的負載分配演算法實現高效且穩定的 負載平衡。隨著現代資訊科技的快速發展，企業和組織需要管理海量資料和執行複 雜運算，這使得分散式系統成為關鍵技術架構。然而，在動態變化的工作負載下， 高效的分配資源仍然是一大挑戰。
研究首先介紹了分散式系統的基本概念和背景，包括節點、任務和排程器等核心元 素。接著，探討了當前的研究現況，並詳細介紹了多種負載分配演算法，Power of 2 Choices 和隨機化負載平衡等。這些演算法在處理負載平衡問題上具有各自的優勢和 限制。
本論文重點在於分析這些演算法在實現負載平衡和維持系統穩定性方面的表現。通 過實驗，我們比較了各演算法在不同情境下的效能，並對其長期穩定性進行了觀察 和評估。結果顯示，僅依靠單一時刻的負載平衡難以保證系統的長期穩定性，需考 慮更複雜的動態負載管理策略。
最終，研究結果有助於理解負載分配演算法在實際應用中的效能表現，並為未來在 分散式系統中實現更高效穩定的負載平衡提供了理論基礎和實踐指南。

The scope of this research is to investigate different load distribution algorithms for achieving efficient and stable load balancing in distributed systems. The objectives are to analyze and compare the performance of various algorithms in terms of load balanc- ing effectiveness and stability over time. The methods used involve implementing and simulating three major load distribution algorithms: Power of Two Choices, Load Re- balancing for Distributed File Systems in Clouds, and Stochastic Load Balancing for Virtual Resource Management in Datacenters. The researchers conducted experiments using real workload data from Microsoft Azure to evaluate the long-term behavior of these algorithms after an initial load balancing operation. The key metrics considered were the average load and variance across nodes over time. The results demonstrate that algorithms considering aggregate resource indicators, such as expected load and load variance, can significantly improve long-term load balancing and stability compared to those relying solely on instantaneous load states.

[1] Amazon Web Services. https://aws.amazon.com.
[2] AzurePublicDataset. https://github.com/Azure/AzurePublicDataset.
[3] Google Cloud Platform. https://cloud.google.com.
[4] Microsoft Azure. https://azure.microsoft.com.
[5] Balanced allocations (extended abstract). pages 593–602, 1994.
[6] Convergence properties of many parallel servers under power-of-d load balancing. arXiv: Probability, 2018.
[7] Cloud game resource scheduling method and device. 2020.
[8] A distributed microservice scheduling optimization method. pages 807–812, 2023.
[9] Laith Mohammad Abualigah and Muhammad Alkhrabsheh. Amended hybrid multi- verse optimizer with genetic algorithm for solving task scheduling problem in cloud computing. The Journal of Supercomputing, 78:740 – 765, 2021.
[10] IsmailM.Ali,KaramM.Sallam,NourMoustafa,RiponChakraborty,MichaelJ.Ryan, and Kim￿Kwang Raymond Choo. An automated task scheduling model using non- dominated sorting genetic algorithm ii for fog-cloud systems. IEEE Transactions on Cloud Computing, 10:2294–2308, 2022.
[11] NikhilBansalandOhadN.Feldheim.Thepoweroftwochoicesingraphicalallocation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 52–63, New York, NY, USA, 2022. Association for Computing Machinery.
[12] Giovanni F. da Silva, Francisco Brasileiro, Raquel Lopes, Morais Fabio, Marcus Car- valho, and Daniel Turull. Qos-driven scheduling in the cloud. Journal of Internet Services and Applications, 11(1), Dec 2020 2020/12//.
[13] Tarun Kumar Ghosh, Krishna Gopal Dhal, and Sanjoy Das. Cloud task scheduling using modified penguins search optimization algorithm. International Journal of Next- Generation Computing, 2023.
[14] Mor Harchol-Balter. Introduction to Probability for Computing. Cambridge University Press, 2023.
[15] Hung-Chang Hsiao, Hsueh-Yi Chung, Haiying Shen, and Yu-Chang Chao. Load re- balancing for distributed file systems in clouds. IEEE Transactions on Parallel and Distributed Systems, 24(5):951–962, 2013.
[16] Anupam Mazumdar and Husam Helmi Alharahsheh. Insights of trends and develop- ments in cloud computing. South Asian Research Journal of Engineering and Technol- ogy, 2019.
[17] Rahul Mishra and Manish Gupta. Cloud scheduling heuristic approaches for load bal- ancing in cloud computing. In 2023 6th International Conference on Information Sys- tems and Computer Networks (ISCON), pages 1–8, 2023.
[18] M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12(10):1094–1104, 2001.
[19] Michael Mitzenmacher and Matteo Dell'Amico. The supermarket model with known and predicted service times. IEEE Transactions on Parallel and Distributed Systems, page 1–1, 2022.
[20] Martin Raab and Angelika Steger. “balls into bins” — a simple and tight analysis. In Michael Luby, José D. P. Rolim, and Maria Serna, editors, Randomization and Approx- imation Techniques in Computer Science, pages 159–170, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.
[21] Manish Saraswat and R.C. Tripathi. Cloud computing: Comparison and analysis of cloud service providers-aws, microsoft and google. In 2020 9th International Confer- ence System Modeling and Advancement in Research Trends (SMART), pages 281–285, 2020.
[22] MahadevSatyanarayanan.Theemergenceofedgecomputing.Computer,50(1):30–39, 2017.
[23] Mohammad Shahrad, Rodrigo Fonseca, Íñigo Goiri, Gohar Chaudhry, Paul Batum, Ja- son Cooke, Eduardo Laureano, Colby Tresness, Mark Russinovich, and Ricardo Bian- chini. Serverless in the wild: characterizing and optimizing the serverless workload at a large cloud provider. In Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC’20, USA, 2020. USENIX Association.
[24] Zhao Tong, Xiaomei Deng, Hongjian Chen, and Jing Mei. Ddmts: A novel dynamic load balancing scheduling scheme under sla constraints in cloud computing. J. Parallel Distributed Comput., 149:138–148, 2021.
[25] Minh-Ngoc Tran and Younghan Kim. A cloud qos-driven scheduler based on deep reinforcement learning. In 2021 International Conference on Information and Commu- nication Technology Convergence (ICTC), pages 1823–1825, 2021.
[26] Rahul Vaze. Index. Cambridge University Press, 2023.
[27] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbe- len, and Jan S. Rellermeyer. A survey on distributed machine learning. ACM Comput. Surv., 53(2), mar 2020.
[28] Haoyu Wang, Zetian Liu, and Haiying Shen. Machine learning feature based job scheduling for distributed machine learning clusters. IEEE/ACM Transactions on Net- working, 31(1):58–73, 2023.
[29] Lei Ying, R. Srikant, and Xiaohan Kang. The power of slightly more than one sample in randomized load balancing. Mathematics of Operations Research, 42(3):692–722, August 2017. Publisher Copyright: © 2017 INFORMS.
[30] Lei Yu, Liuhua Chen, Zhipeng Cai, Haiying Shen, Yi Liang, and Yi Pan. Stochastic load balancing for virtual resource management in datacenters. IEEE Transactions on Cloud Computing, 8(2):459–472, 2020.