Application of queueing theory methods for estimating synchronization parameters of distributed computing systems

The paper discusses the approach to estimating the synchronization parameters of distributed computing systems, based on the application of mass queueing theory algorithms. The proposed approach is built upon the use of statistical approaches by means of the maximum likelihood method as well as a number of numerical algorithms to find optimal parameters of synchronization systems. The application of mass queueing theory methods and the Ricart-Agraval model helps to efficiently adapt a distributed system in terms of an optimal solution to the synchronization problem. The employment of statistical approaches in reliance on the calculation of the likelihood function allows one to obtain statistical estimates of the input and output flow intensities of resource synchronization requirements, which enables optimization of the synchronization system with a heterogeneous hardware configuration and makes it possible to determine the maximum allowable flow of requirements for this system. A computational experiment was conducted utilizing Spark as a basic distributed computing system. When conducting an experiment, the algorithm analyzed in the article is used instead of the standard synchronization algorithm included in the Spark assembly. Relations between synchronization time and volume of data transmitted between units of the analyzed system are obtained, which provides a means of calculating parameters of the synchronization system as well as selecting optimal values for the given system. The practical results presented in the scientific study prove the correctness of the theoretical approaches used in the process of creating effective systems for synchronizing distributed resources for the Spark platform in question.

1. Gnedenko B.V., Kovalenko N.N. Vvedenie v teoriyu massovogo obsluzhivaniya. Moscow, Nauka; 1966. 431 с. (In Russ.)

2. Kendall M. Statisticheskie vyvody i svyazi. Moscow, Nauka; 1973. 878 p. (In Russ.)

3. Livshic A.L., Malc E.A. Statisticheskoe modelirovanie sistem massovogo obsluzhivaniya. Moscow, Sov. Radio; 1978. 248 p. (In Russ.)

4. Riordan J. Veroyatnostnye sistemy obsluzhivaniya. Moscow, Svyaz; 1966. 184 с. (In Russ.)

5. Azarnova T.V., Polukhin P.V. Distributed computing systems synchronization modeling for solving machine learning tasks. Journal of Physics: Conference Series. 2021;1902(1):012050.

6. Magnus Ya.R., Neudecker H. Matrix differential calculus with application in statistics and econometrics. Oxford, Wiley; 1988. 496 p.

7. Kobzar A.I. Prikladnaya matematicheskaya statistika. Moscow, Fizmatlit; 2006. 816 p. (In Russ.)

8. Леман Э. Проверка статистических гипотез. М.: Наука; 1987. 408 p. (In Russ.)

9. Ricart G., Agrawala A.K. An optimal algorithm for mutual exclusion in computer networks. Communications of the ACM. 2021;1(2):9–17.

10. Berns B. Raspredelennye sistemy. Patterny proektirovaniya. Saint Petersburg, Piter; 2019. 224 p. (In Russ.)

11. Zaharia M., Chowdhury M, Das T, Dave A, McCauley M, Franklin M, Shenker S, Stoica I. Resilent Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. NSDI. 2012;1–15.

12. Chowdhury M., Ma J., Jordan M.I., Stoica I. Managing Data Transfers in Computer Clusters with Orchestra. SIGCOMM. 2011;41(4):98–109.