Email this article 
Stochastic models for time complexity of computing tasks: I. Development principles, statistical data mining, identification problems
- Authors: Borisov A.V.1, Ivanov A.V.1
-
Affiliations:
- Federal Research Center “Computer Science and Control” of Russian Academy of Sciences
- Issue: No 1 (2024)
- Pages: 22-34
- Section: INFORMATION PROCESSING AND IDENTIFICATION
- URL: https://journals.rcsi.science/0002-3388/article/view/262522
- DOI: https://doi.org/10.31857/S0002338824010037
- EDN: https://elibrary.ru/IXTIMV
- ID: 262522
Cite item
Open Access
Access granted
Abstract
The paper contains the first part of an investigation devoted to the design of the mathematical models for the execution time of user tasks carried out on the virtual calculating nodes. We suppose that the execution time is a random value with the mean and variance depending on the node resources, task parameters, and the current characteristics of the node state. We discover the key features of the mean and variance functions and specify some of their particular cases. Both the mean and variance functions depend on the unknown parameters, and the design of the stochastic model for the time complexity leads to the parameter identification in the form of the generalized maximum likelihood estimates under the heterogeneous statistical information. The paper also contains recommendations concerning the gathering and subsequent usage of this information: the node testbed preparation, stress test planning, and the obtained data processing. The specific illustrating examples of the proposed mathematical model will be presented in the subsequent parts of the investigation.
Full Text
About the authors
Andrey V. Borisov
Federal Research Center “Computer Science and Control” of Russian Academy of Sciences
Author for correspondence.
Email: ABorisov@frccsc.ru
Russian Federation, Moscow
Alexey V. Ivanov
Federal Research Center “Computer Science and Control” of Russian Academy of Sciences
Email: AIvanov@frccsc.ru
Russian Federation, Moscow
References
- Sirohi P., Agarwal A., Maheshwari P. A Survey on Augmented Virtual Reality: Applications and Future Directions // Seventh Intern. Conf. on Information Technology Trends (ITT). Abu Dhabi, United Arab Emirates, 2020, P. 99—106.
- Gupta P., Krishna C., Rajesh R. et al. Industrial Internet of Things in Intelligent Manufacturing: a Review, Approaches, Opportunities, Open Challenges, and Future Directions // Int. J. Interact. Des. Manuf. 2022.
- Parveen I., C.A., Anjali, O., Sunder, R. Internet of Things: A Review on Its Applications // Information and Communication Technology for Competitive Strategies (ICTCS 2021). Lecture Notes in Networks and Systems. 2021. V. 400. P. 123—134.
- Fraga-Lamas P., Fernández-Caramés T., Suárez-Albela M., Castedo L., González-López M. A Review on Internet of Things for Defense and Public Safety // Sensors. 2016. V. 16. Iss. 10. P. 1644.
- Abu Talib M., Abbas S., Nasir Q., Mowakeh M. Systematic literature review on Internet-of-Vehicles Communication Security //Intern. J. of Distributed Sensor Networks. 2018. V. 14. P. 12.
- Nocedal J., Wright S. Numerical Optimization. N.Y.: Springer, 2006. 686 p.
- Bertsekas D. Convex Optimization Algorithms. Belmont: Athena Scientific, 2015. 576 p.
- Kearns M. The Computational Complexity of Machine Learning. Cambridge: MIT Press, 1990. 182 p.
- Teller S., Séquin C. Visibility preprocessing for interactive walkthroughs // Proc. 18th Annual Conf. on Computer Graphics and Interactive Techniques. 1991. P. 61—70.
- Интриллигатор М. Математические методы оптимизации и экономическая теория. М.: Прогресс, 1975. 600 c.
- Хьюбер П. Робастность в статистике. М.: Мир, 1984. 304 c.
- Броневич А., Лепский А. Нечеткие модели анализа данных и принятия решений. М.: ВШЭ, 2022. 264 c.
- Pankov A., Siemenikhin K. Minimax Estimation for Singular Linear Multivariate Models with Mixed Uncertainty // J Multivariate Analysis. 2007. V. 98. Iss. 1. P. 145—176.
- Borisov A. Minimax Estimation in Regression under Sample Conformity Constraints // Mathematics. 2021. V. 9. P. 1080.
- Ширяев А. Вероятность. М.: Физматлит, 1989. 644 c.
- Tukey J. Exploratory Data Analysis. Boston: Addison-Wesley, 1977. 712 p.
- Семенихин К. Двусторонняя вероятностная граница для симметричной унимодальной случайной величины // АиТ. 2019. № 3. С. 103—122.
- Ion R., Klaassen C., van der Heuvel E. Sharp Inequalities of Bienaymé-Chebyshev and Gauß Type for Possibly Asymmetric Intervals Around the Mean // TEST. 2023. https://doi.org/10.1007/s11749-022-00844-9
- Демиденко Е. Линейная и нелинейная регрессии. М.: Финансы и статистика, 1981. 304 c.
- Мудров В., Кушко В. Метод наименьших модулей. М.: URSS, 2022. 64 c.
- Koenker R . Quantile Regression. Cambridge: Cambrige University Press, 2005. 368 p.
- https://bapco.com/products/sysmark-25/
- https://benchmarks.ul.com/pcmark10
- https://www.spec.org/cpu2017/
- https://www.tpc.org/tpce/
- Ермаков С., Козлов В., Жиглявский А. Математическая теория планирования эксперимента. М.: Наука, 1983. 392 c.
- Black R. Managing the Testing Process, 3rd Edition: Practical Tools and Techniques for Managing Hardware and Software Testing. Indianapolis: Wiley, 2009. 672 p.
- Льюнг Л. Идентификация систем: Теория для пользователя. М.: Наука, 1991. 432 c.
- Ивченко Г., Медведев Ю. Математическая статистика. М.: URSS, 2014. 608 c.
- Пантелеев А., Метлицкая Д., Алешина Е. Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы. М.: Вузовская книга, 2013. 244 c.
Supplementary files
