|
Abstract.
To effectively solve the problem of developing elastic distributed algorithms that adapt to dynamic workloads and resource availability, a new elastic computational model based on pattern-dependent (PD) languages and their recognizers, fractal finite state automata (FFA), is introduced. The relationship between PD languages and geometric fractals is given. A method for designing elastic algorithms is proposed, which consists of two steps: first, extracting invariants from the algorithm by representing it as a chain of transforming multi-valued functions; and second, applying these invariants as operational symbols within the PD and FFA. The method is exemplified for developing an elastic algorithm for a binary tree based on the FFAs. This solution can be mapped onto an elastic computing network, where the nodes of the tree are implemented as servers or containers. Efficiency is achieved during the transition from simulation modeling to the development of a control system by minimizing additional transformations. The elastic computational model functions as the core of the control system, facilitating a more rapid and cost-efficient transition to practical system management. This advantage is supported by a comparative analysis presented in the paper, highlighting the proposed method's effectiveness and universality over the existing approaches.
Keywords:
pattern dependent languages, fractal finite state automata, elastic algorithms, elastic computing.
DOI 10.14357/20718632250412
EDN YRJJIW
Стр. 121-133.
References
1. Semenov A.S. Hyperagent smart factories based on fractal Petri nets: ensuring elasticity and sustainability. In: Proc. 10th Int. Conf. Control, Decision and Information Technologies (CoDIT). Publisher: IEEE; Malta: 2024. pp. 425-430. doi: 10.1109/CoDIT62066.2024.10708431. 2. Serrano M.A., et al. An elastic software architecture for extreme-scale big data analytics. In: Curry E., Auer S., Berre A.J., Metzger A., Perez M.S., Zillner S. (eds) Technologies and applications for big data value. Cham: Springer; 2022. pp. 1-10. doi: 10.1007/978-3-030-78307-5_5. 3. Marangozova-Martin V., de Palma N., El Rheddane A. Multi-level elasticity for data stream processing. IEEE Transactions on Parallel and Distributed Systems. 2019; 30(10): 2326-2337. doi: 10.1109/TPDS.2019.2907950. 4. Ulam M. Cellular automata. Proceedings of the International Congress of Mathematicians. 1960; 1: 45-49. 5. von Neumann J. Theory of self-reproducing automata. In: Burks A.W. (ed) Urbana: University of Illinois Press; 1966. pp. 1-346. 6. Wolfram S. A new kind of science. Champaign, IL: Wolfram Media; 2002. 7. von Neumann J., Morgenstern O. Theory of games and economic behavior. New York, NY: Wiley; 1944. pp. 188. ISBN 0-471-99936-5. 8. Hopcroft J.E., Ullman D.P. Introduction to automata theory, languages, and computation. 1st ed. Shaidullin M.M. (ed) Boston, MA: Addison-Wesley Publishing Company; 1979. pp. 328. (Computer Science Series). ISBN 0-201-03456-3. 9. Semenov A.S. Essentials of fractal programming. In: Jain L.C., et al. (eds) Smart innovation, systems and technologies. Advances in theory and practice of computational mechanics. Springer-Verlag; 2020. pp. 373-386. doi: 10.1007/978-981-15-2600-8_25. 10. Semenov A.S. Prototype based programming with fractal algebra. AIP Conference Proceedings. 2019; 2181: 1-5. doi: 10.1063/1.5135669. 11. Semenov A.S. Graph-based dynamic analysis of elastic systems. In: Proc. 7th Int. Conf. Control, Decision and Information Technologies (CoDIT). 2020. vol. 1. pp. 65-70. doi: 10.1109/CoDIT49905.2020.9263986. 12. Glushkov V.M. Abstract theory of automata. Uspekhi Matematicheskikh Nauk. 1961; 16(5): 476. 13. Moore E.F. Gedanken-experiments on sequential machines. In: Automata Studies; 1956. 14. Mili E. Finite state machines and their application. 1967. 15. Back R.-J. Invariant based programming: basic approach and teaching experience. Formal Aspects of Computing. 2008; 20(1): 1-14. ISSN 0934-5043, 1433-299X. 16. Andreolia R., Zhao J., Cucinotta T., Buyya R. CloudSim 7G: an integrated toolkit for modeling and simulation of future generation cloud computing environments. arXiv:2408.13386 [cs.DC]; 2024. 17. Horzela M., Casanova H., Giffels M., Gottmann A., Hofsaess R., Quast G., Tisbeni S.R., Streit A., Suter F. Modeling distributed computing infrastructures for HEP applications. arXiv:2403.14903 [cs.DC]; 2024. 18. Saket S., Chandela V., Kalim M.D. Real-time event joining in practice with Kafka and Flink. arXiv:2410.15533 [cs.SE]; 2024. 19. Turin G., Borgarelli A., Donetti S., Damiani F., Johnsen E.B., Tarifa S.L.T. Predicting resource consumption of Kubernetes container systems using resource models. arXiv:2305.07651; 2023. 20. Guedelha N., Pasandi V., L'Erario G., Traversaro S., Pucci D. A flexible MATLAB/Simulink simulator for robotic floating-base systems in contact with the ground: theoretical background and implementation details. arXiv:2405.08092; 2024. 21. McCormick E., Lang H., de Silva C.W. Dynamic modeling and simulation of a four-wheel skid-steer mobile robot using linear graphs. arXiv:2110.00323 [cs.RO]; 2021. 22. TensorFlow. Model optimization toolkit. Available at: https://www.tensorflow.org/model_optimization. 23. Adam C., Gaudou B. An agent-based model of modal choice with perception biases and habits. arXiv:2406.02063 [cs.CY]; 2024. 24. Crownover R. Introduction to fractals and chaos. London: Jones and Bartlett Publishers; 1995.
|
