CONSTRUCTIVE MODEL FOR GENERATING DAG STRUCTURES OF WORKLOADS
DOI:
https://doi.org/10.34185/1991-7848.itmm.2026.01.057Keywords:
information technology, software engineering, constructive-synthesizing modeling, directed acyclic graph, formal grammars, graph grammars, task scheduling, Kubernetes, container orchestration, workload generationAbstract
A constructive model for generating DAG structures of workloads for testing Kubernetes cluster schedulers is proposed. The model is based on the generalized constructor formalism and specializes its components for the domain of directed acyclic task graphs. The substitution mechanism is formalized as a special case of node replacement graph grammar with four rule types: attribute assignment, subgraph substitution, replication, and algorithmic generation. An attribute system extending Knuth’s attribute grammars to graph structures is introduced. Preservation of acyclicity under each substitution and termination of the generation process are formally proved. The constructor is implemented in Python with a declarative YAML DSL. Experimental validation on a set of 100 generated DAGs confirms the practical applicability
of the model.
References
Chomsky N. Three models for the description of language // IRE Trans. on Information Theory. — 1956. — Vol. 2, No. 3. — P. 113–124.
Knuth D. E. Semantics of context-free languages // Mathematical Systems Theory. — 1968. — Vol. 2, No. 2. — P. 127–145.
Shynkarenko V. I., Ilman V. M. Constructive-Synthesizing Structures and Their Grammatical Interpretations. I. Generalized Formal Constructive-Synthesizing Structure // Cybernetics and Systems Analysis. — 2014. — Vol. 50, No. 5. — P. 655–662. DOI: 10.1007/s10559-014-9655-z.
Skalozub V., Ilman V., Shynkarenko V. Ontological support formation for constructive-synthesizing modeling of information systems development processes // Eastern-European Journal of Enterprise Technologies. — 2018. — Vol. 5, No. 4(95). — P. 55–63. DOI: 10.15587/1729-4061.2018.143968.
Rozenberg G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 1: Foundations. — World Scientific, 1997.
Cordeiro D., Mounié G., Perarnau S., Trystram D., Vincent J.-M., Wagner F. Random graph generation for scheduling simulations // Proc. 3rd International ICST Conference on Simulation Tools and Techniques (SIMUTools 2010). — 2010. — P. 1–10. DOI: 10.4108/ICST.SIMUTOOLS2010.8667.
Canon L.-C., Sayah M., Héam P.-C. A Comparison of Random Task Graph Generation Methods for Scheduling Problems // Euro-Par 2019. LNCS, vol. 11725. — Springer, 2019. — P. 61–73.
