Stochastic models for time complexity of computing tasks: I. Development principles, statistical data mining, identification problems

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.