=Paper=
{{Paper
|id=Vol-1940/paper08
|storemode=property
|title=Stochastic Modelling of Large-Scale Distributed Computer Systems Functioning with Group Restorations
|pdfUrl=https://ceur-ws.org/Vol-1940/paper08.pdf
|volume=Vol-1940
|authors=Valery Pavsky,Kirill Pavsky
}}
==Stochastic Modelling of Large-Scale Distributed Computer Systems Functioning with Group Restorations==
<pdf width="1500px">https://ceur-ws.org/Vol-1940/paper08.pdf</pdf>
<pre>
   Stochastic Modelling of Large-Scale Distributed
Computer Systems Functioning with Group Restorations

                             Valery Pavsky 1, and Kirill Pavsky 2
    1
        Kemerovo Institute of Food Science and Technology (University), Kemerovo, Russia
                                     pavva46@mail.ru

    2
        Rzhanov Institute of Semiconductor Physics Siberian Branch of Russian Academy of
                   Sciences, pr. Lavrentieva, 13, Novosibirsk, 630090, Russia
                                      pkv@isp.nsc.ru



         Abstract.
         The model of functioning of distributed computer systems with group restora-
         tions of failed machines is considered. The model is formalized in the form of a
         system of differential equations, in which are unknown probabilities of the
         states. The paper proposes solutions for calculating the mathematical expecta-
         tion of the number of efficient machines and variances, which are the basis for
         creating indices of potential robustness.
         The investigation of the functioning of the CS under the assumption of the va-
         lidity of the exponential law of failure of computers makes it possible, due to a
         well-developed theory, to obtain profound results, in contrast to the use of other
         distribution laws. And the obtained analytical solutions can be used for rapid
         analysis of the functioning of the CS.

         Keywords: distributed computer systems, mathematical model, group restora-
         tion, number of working machines, analytical solutions.


1        Introduction

The problem of the reliability of high-performance scalable computing devices, in-
cluding supercomputers and computer systems [1], increases with the number of ele-
mentary machines (EM) [2], the number of which in such systems ranges from sever-
al tens to hundreds of thousands [3]. Practice shows that in scalable computing sys-
tems (CS) the time between different types of failures can be measured by hours [4,5].
The preservation of the efficiency of the CS in the conditions of failures [6-8], the
analysis of functioning with regard to robustness, is an urgent task.
This work is devoted to the development of means for analyzing the efficiency of the
operation of larger-scale distributed CS [9, 10]. The queuing theory apparatus is used
as an analysis tool.
The paper proposes formulas for calculating the mathematical expectation and va-
riance of the number of working machines, which are the basis for creating indicators
of potential robustness in group recovery [2]. The indices of potential robustness of
                                                                                        61


the CS take into account the fact that in the solution of problems all the working EMs
are used, the number of which is actually instant. This assumes that parallel programs
of complex tasks, when implemented on survivable CS, are capable of using the total
performance of all working EM systems. Assuming mathematical idealization, CS
can be regarded as a stochastic object.


2      Model of the CS functioning

A stochastic model of the distributed CS operation is proposed, in which the EMs are
not absolutely reliable [2]. Each of them fails with  intensity. Out of order EM gets
into the restoration system and is waiting for resoration. At random moments of time,
the recovery is exercised by groups in r EM with  intensity (Fig.1). We believe that
at the initial time the system contains n EMs. As performance indices (evaluation of
potential viability), we use numerical characteristics – the mathematical expectation
of the number of effective EMs and its variance [2].
                       Computer System                             Restoration System



                                                                          
                                                 r           r

                                           μ           μ           μ
                                                            



                                                       k
                                .




Fig. 1. Model of the functioning of a scalable CS in the group recovery of failed EM.

In constructing the model of the functioning of the CS, we use the methods of
queuing theory, in which models of this class are formulated according to the tried-
and-tested method – a system of differential equations is compiled, and the probabili-
ty distribution is considered as unknown functions. The analytical solution of such
systems is far from always available, even stationary [2]. Assuming further mathemat-
ical idealization of the model, we believe that the number of EMs in the CS is poten-
tially infinite, which is permissible because of its scalability. From the formalized
system of differential equations of the model, we find an analytical solution, directly
for the moments, bypassing the probability distribution.
62


3      Mathematical Model

The queuing system (QS) with an infinite number of channels receives a Poisson
stream of packets with  intensity [11, 12]. Each packet consists of r requirements.
At any fixed time t  [ 0 ,  ) , the QS is in one of a number of incompatible states C k -
where k is the number of requirements in the QS, including undeserved requirements.
The service time of each requirement is subject to an exponential distribution with a
parameter  . If the system is in the C k state, then one of the k requirements leaves
the system with the k intensity. It is required to find the mathematical expectation
of the M ( t ) state number, in which the system is located when servicing the re-
quirements and the corresponding variance D( t ) , provided that M ( 0 )  n , D( 0 )  0 .
Figure 2 shows a graph-scheme of QS states that allows us to better understand the
relationship between the formulation of the model and its formalization by a system
of differential equations.
                          μ        μ                              μ                   μ                 μ
     c0         c1            c2             cr         cr1               cj      c j r      c j r 1   
           λ         2λ                   rλ         (r 1)λ                jλ        ( j  r)λ ( j  r 1)λ


Fig. 2. Graph-scheme of QS states, for the scalable CS operation model.

 Pk ( t ) denotes the probability that at the instant t the QS is in the state C k , k = 0,1,…
The system of differential equations has the form:
            P' ( t )   P ( t )  P ( t ),
            0               0         1
            '
            Pk ( t )  (   k )Pk ( t )  ( k  1 )Pk 1( t ), 0  k  r ,(*)           (1)
            '
            Pk ( t )  (   k )Pk ( t )  Pk  r ( t )  ( k  1 )Pk 1( t ), k  r .
To find the mathematical expectation and variance, we apply the method of generat-
ing functions. We transform the system of equations (1) so that in it the middle equa-
tion (*), with sliding parameter k, would be obtained from the last equation, at 0<k<r.
For this, we set Pk  r ( t )  0 , 0  k  r , then the system (1) will look as follows:
                      P' ( t )   P ( t )  P ( t ),
                          0             0         1
                                                                                                                         (2)
                          '
                       Pk ( t )  (   k )Pk ( t )  Pk  r ( t )  ( k  1 )Pk 1( t ),
In accordance with the formulation of the model, we give the initial conditions
                          Pn ( 0 )  1 ; Pk ( 0 )  0 , k  n                   (3)
and the normalization condition, which is a consequence of the formulation of the
model,
                                          
                                          Pk ( t )  1 .                                                                 (4)
                                         k 0
                                                                                                                  63


To solve the system (2), taking into account (4), we introduce the generating function
                                                      
                                        F ( z , t )   z k Pk ( t ) .                                            (5)
                                                     k 0
Multiplying the corresponding equation k of system (2) by z k and summing, we
obtain
                                                                                        
  z k Pk' ( t )     z k Pk ( t )    kz k Pk ( t )    z k Pk r ( t )    ( k  1 )z k Pk 1( t )
k 0                    k 0                 k 1                  k 0                    k 0
Expressing each term of the resulting equation in terms of the generating function and
reducing such terms, we obtain a linear equation for the generating function
                                                                       
                  F ( z , t )    ( 1  z r )F ( z , t )   ( 1  z ) F ( z , t ) . (6)
               t                                                       z
To find the mathematical expectation M ( t ) and the corresponding variance D( t ) ,
we use the method of moments [13].
We take the derivative with respect to the variable z from the right and left sides of
(6), then
      2                                                                                        2
          F ( z ,t )  rz r 1F ( z ,t )   ( 1  z r ) F ( z ,t )   F ( z ,t )   ( 1  z )      F ( z ,t ) .(7)
     zt                                                z             z                        z 2
Assume  is a random variable characterizing the number of requirements in the QS.
From (5) and the properties of the generating functions [13, 14] it follows that
                                                                                                2
                                                2                            
                   M          F ( 1 ) , а D      F ( 1 )  F ( 1 )   F ( 1 ) .
                             z                   2           z          z     
                                                  z
After the corresponding transformations over (7) we obtain
                     
                      t M ( t )  M ( t )  r ,
                     
                                                                                                                (8)
                      Q( t )  2Q( t )  2rM ( t )  r( r  1 ) ,
                      t
                      D( t )  Q( t )  M ( t )  M 2 ( t ),
                     
                     
where, on the basis of (3), M ( 0 )  n , D( 0 )  0 .
The solution for (8), taking (3) into account, will be
                  r         r   t
       M ( t )     n   e         ,
                                
                   2       r         r ( r  1 )  2t r r          r    t
        D( t )  ( n  n  ( 2n                  ))e      (    2 n     e      )  (9)
                                            2                          
        r( r  1 )
                      M ( t )  M 2( t )
              2
For the stationary regime we have
64


                                            r
                                    M          ,
                                             
                                          r 2   r
                                       D             ,                           (10)
                                               2
                                               2
                                       r   r .
                                                 2
     Figure 3 shows the calculation of the mathematical expectation with allowance for
     dispersion by formulas (9) at   10 1 1/hr,   103 1/hr, r  20 , n  104 EM.




Fig. 3. The average number of working machines with variance.

From formulas (9) and their graphical implementation (Fig. 3), it is also evident that
the robustness of the CS and high performance is provided by two thousand EM,
while reliability should be calculated on the basis of ten thousand EM. Therefore, in
order to achieve sufficient robustness, given the volume of the aircraft, it is necessary
to increase the reliability of the element base and other parameters associated with the
process of executing parallel programs.
In Fig. 4 shows an example where the system is initially in a state of equilibrium be-
tween failure and recovery ((9) and (10)) for   5  10 2 1/hr,   104 1/hr, r  20 ,
 n  104 EM. In Fig. 5 also shows the calculation of the root-mean-square deviation
for this case. It can be seen how quickly the system enters a stationary mode and it is
possible to estimate the limits of its potential performance.
                                                                                   65




Fig. 4. The average number of working machines with variance.




Fig. 5. Calculation of variance.


4       Conclusion

Calculations of the mathematical expectation and dispersion of the number of work-
ing machines in distributed scalable computing systems use a technique designed
primarily to assess the effectiveness of the functioning of predictive and projected
computing systems. Here the mathematical apparatus is used as a research method,
demonstrating not only the result, but also the prospects for its development. This is
the main advantage of analytical solutions - internal information meaningfulness for-
mulas to numerical and algorithmic approaches, using this device as a research tool.
The solution is obtained by the method of moments [13]. In the theory of queuing of
this type, models are usually formalized by systems of differential equations with
unknowns that form a probability distribution. As a rule, this is sufficient for con-
structing a probability space. Consequently, any probabilistic characteristics asso-
66


ciated with the random value of this space can be obtained one way or another. In our
case, it is impossible to find an exact solution of the probability distribution, since,
even in the steady-state regime, complications arise that lead to an approximate solu-
tion. The method of moments makes it possible to find an exact solution for the mo-
ments of any order. In addition, finding an exact solution allows us to obtain addition-
al information that is inaccessible to an approximate solution. For example, the num-
ber n, EM in the computer system, appears conditionally (in the initial conditions and
in the formulas for the transitional regime), but is absent in the systems of differential
equations (1), (2) and in the formulas of the stationary regime – this is the property of
the Markov processes. In addition to the quantitative evaluation of the productivity of
the QS, a qualitative assessment is obtained – it is impossible to achieve any desired
pre-set performance by simply increasing the computing system by elementary ma-
chines, without improving their parameters.


References
 1. Dongarra J. J., A. J. van der Steen High-performance computer systems: Status and out-
    look, Acta Numerica (2012), pp. 1–96.
 2. Khoroshevsky V.G. Architecture of computer systems. Moscow: Bauman MSTU, 2008, p.
    520.
 3. TOP500 Supercomputers Official Site. TOP500 Lists [website] [Electronic resource] /
    URL: http://www.top500.org (16.05.2017).
 4. Nikolic S. High Performance Computing Directions: The Drive to ExaScale Computing. //
    Proceedings of the International Scientific Conference "Parallel Computing Technologies
    (ПаВТ’2012). –Novosibirsk, 2012, URL: http://pavt.susu.ru/2012/talks/Nikolic.pdf
    (16.05.2017).
 5. Schroeder В., Gibson Garth A. A large-scale study of failures in high-performance compu-
    ting systems // Proceedings of the International Conference on Dependable Systems and
    Networks (DSN2006), Philadelphia, PA, USA, June 25-28, 2006, 10 р.
 6. Kalyaev I.A., Korobkin V.V., Melnik E.V., Malakhov I.V. Fault-tolerant control computer
    complex of a VVER-type reactor of a rechargeable nuclear reactor // Mechatronics, Auto-
    mation, Control. - 2003.-No. 3. P.143-146.
 7. S. Di, M. S. Bouguerra, L. Bautista-Gomez, and F. Cappello. Optimization of multilevel
    checkpoint model for large scale hpc applications. In Parallel and Distributed Processing
    Symposium, 2014 IEEE 28th International, pages 1181–1190, May 2014.
 8. Korneev V.V., Semenov D.V., Telegin P.N., Shabanov B.М. Fault-tolerant decentralized
    grid resource management // Izvestiya Vuzov. Electronics. 2015. No. 1, P. 83-89.
 9. Vishnevsky, V.M. Theoretical Foundations of Computer Network Design. V.M. Vish-
    nevsky. - Moscow: Technosphere, 2003. - 512 p.
10. Khoroshevsky V.G. Models of analysis and organization of large-scale distributed com-
    puter systems. // Electronic modeling. - Kiev, 2003. - Vol. 25, No. 6.
11. Saati T.L. Elements of queuing theory and its applications. Ed. 3rd. - Moscow: The Book
    House "LIBROKOM", 2010. - 520p.
12. Kleinrok L. Queuing theory. M .: Mechanical Engineering, 1979. - 432 p.
13. Khoroshevsky V.G., Pavsky V.A. Calculating the efficiency indices of distributed comput-
    er system functioning// Optoelectronics, Instrumentation and Data Processing. – 2008. – V.
    44. – №2. – P. 95–104.
                                                                               67


14. Gibson Garth A. [Electronic resources] // Analyzing failure data: [сайт]. URL:
    http://www.pdl.cmu.edu/FailureData/ (27.05.2017 г.).

</pre>