Author Guidelines for 8

A.  Transition time measurement model 

In  a  distributed  system,  each  machine  writes  log 

message  sequences  to  its  local  disc  independently. 

Therefore,  different  training  state  sequences  may  be 

derived  from  logs  in  different  machines.  Suppose  we 

have M machines in a distributed system. For each state 

transition in the FSA, e.g. from S

a

 to S

b

, the time inter-

vals between two adjacent states (S

a

, S

b

) in the training 

state sequences produced by i

th

 machine are denoted as 

𝜏

𝑖

1

(𝑆

𝑎

, 𝑆

𝑏

) ,   𝜏

𝑖

2

(𝑆

𝑎

, 𝑆

𝑏

) ,…,  𝜏

𝑖

𝐾

𝑖

(𝑆

𝑎

, 𝑆

𝑏

) ;  1 ≤ 𝑖 ≤ 𝑀 . 

Here, K

i

 is the total number of the time intervals in all 

state sequences produced by the i

th

 machine. 

We use a Gaussian model to present the distribution 

of the state transition interval. In practice, the computa-

tional  capacity  of  machines  in  a  distributed  system  is 

often  heterogeneous. The different  computing  capacity 

of machines results in the state transition time intervals 

in different machines being  quite different. In order to 

handle this problem, we introduce a capacity parameter 

for  each  machine.  Our  model  contains  machine  inde-

pendent 

Gaussian 

distribution 

parameters 

{

𝜇 𝑆

𝑎

, 𝑆

𝑏

 ,  𝜎

2

(𝑆

𝑎

, 𝑆

𝑏

)} and machine dependent capaci-

ty  parameters  {

𝜆

1

 𝑆

𝑎

, 𝑆

𝑏

 ,𝜆

2

 𝑆

𝑎

, 𝑆

𝑏

 ,…, 𝜆

𝑀

(𝑆

𝑎

, 𝑆

𝑏

)}. 

Here, 

the 

Gaussian 

distribution 

𝑁(𝜇 𝑆

𝑎

, 𝑆

𝑏

 , 𝜎

2

 𝑆

𝑎

, 𝑆

𝑏

 ) is used to represent the distri-

bution of the state transition time on an imaginary com-

puter  with  a  standard  computing  capacity.  It  is  only 

determined by the property of the specified state transi-

tion, and does not depend on the property of any specif-

ic machine. The computers’ properties are modeled by 

the  computers’  computing  capacity  parameters 

𝜆

𝑖

(𝑆

𝑎

, 𝑆

𝑏

), 1 ≤ 𝑖 ≤ 𝑀.  The  computers’  computing  ca-

pacity  parameters  are  also  associated  with  the  state 

transition,  because different  state  transitions often cor-

respond  to  different  computing  tasks  and  the  same 

computer may have a different computing capacity un-

der different work load characteristics. 

In  this  subsection,  because  the  state  transition  is 

specified, we abridge state indicators in expressions or 

formulas for simplicity. We assume that the mean value 

of state transition time in the i

th

 machine is proportional 

to its computing capacity parameter 

𝜆

𝑖

, and the variance 

is  proportional  to 

𝜆

𝑖

2

.  With  that  assumption,  the  ob-

tained transition time instances in the i

th

 machine satisfy 

the  Gaussian  distribution 

𝑁(𝜆

𝑖

𝜇, (𝜆

𝑖

𝜎)

2

), 1 ≤ 𝑖 ≤ 𝑀 . 

We  further  assume  that  the  obtained  transition  time 

instances are independent, and then the likelihood func-

tion is as follows. 

𝑝 𝜏

1

1

, 𝜏

1

2

, … , 𝜏

1

𝐾

1

, 𝜏

2

1

, 𝜏

2

2

, … , 𝜏

2

𝐾

2

, … , 𝜏

𝑀

1

, … , 𝜏

𝑀

𝐾

𝑀

   

=  

  

𝑁(𝜏

𝑖

𝑗

; 𝜆

𝑖

𝜇, (𝜆

𝑖

𝜎)

2

)

𝐾

𝑖

𝑗 =1

 

𝑀

𝑖=1

   

             (1) 

With the variable substitutions of 

𝛼

𝑖

= 𝜆

𝑖

𝜇 and 𝛽 =

𝜎

2

𝜇

2

, 

we can obtain the log-likelihood function: 

𝐿 𝛼

1

, 𝛼

2

, … , 𝛼

𝑀

, 𝛽   

= −  

 

[2ln 𝛼

𝑖

+ ln 𝛽 +

1

𝛽

(1 −

𝜏

𝑖

𝑗

𝛼

𝑖

)

2

]

𝐾

𝑖

𝑗 =1

𝑀

𝑖=1

               (2) 

According  to  the  Maximum  Likelihood  Estimation 

criterion,  the  optimal  parameters  should  maximize 

𝐿 𝛼

1

, 𝛼

2

, … , 𝛼

𝑀

, 𝛽 

.  Because  the  optimal  parameters 

should  satisfy  that  the  partial  differentiates  of 

𝐿 𝛼

1

, 𝛼

2

, … , 𝛼

𝑀

, 𝛽  equal to 0, we have: 

---

 

 

 

 

 

 

𝛼

𝑖

=

   

𝜏

𝑖

𝑗

𝐾𝑖

𝑗 =1

 

2

+4𝐾

𝑖

𝛽  

𝜏

𝑖

𝑗 2

𝐾𝑖

𝑗 =1

 −  

𝜏

𝑖

𝑗

𝐾𝑖

𝑗 =1

 

2𝐾

𝑖

𝛽

, 1 ≤ 𝑖 ≤ 𝑀

𝛽 = ( 

 

(𝛼

𝑖

− 𝜏

𝑖

𝑗

)

2

)

𝐾

𝑖

𝑗 =1

𝑀

𝑖=1

( 

𝐾

𝑖

𝛼

𝑖

2

𝑀

𝑖=1

)

 

               

         

(3) 

However,  there  is  no  closed  form  solution  to  the 

above equation group; we can only use an iterative pro-

cedure to obtain an approximation of the optimal para-

meters. It could be proved that after each iteration step, 

the  value  of 

𝐿 𝛼

1

, 𝛼

2

, … , 𝛼

𝑀

, 𝛽 

 increases.  The  iterative 

procedure is shown in Table 2. When the difference of 

β in two iterations is small enough (< Th

β

), the iterative 

procedure terminates.  

Finally, we  can obtain the  transition  time  measure-

ment model: the transition time from S