Stochastic Models for the Time Complexity of Computing Tasks: I. Development Principles, Statistical Data Mining, and Identification Problems

This paper contains the first part of a study on the design of mathematical models for the execution time of user tasks on virtual calculating nodes. It is assumed 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 time complexity leads to parameter identification in the form of the generalized maximum likelihood estimates under heterogeneous statistical information. This paper also contains recommendations concerning the gathering and subsequent use of this information: the node testbed preparation, stress test planning, and processing of the data obtained. Specific illustrating examples of the proposed mathematical model will be presented in the subsequent parts of the study.