# A Time-Series Model for Varying Worker Ability in Heterogeneous Distributed Computing Systems
## 2 Preliminaries
### Model Assumptions  
For the task assigned at time \(t\), we assume the time taken for calculating an inner product of a row of \(A_{i,t}\); the input vector \(\mathbf{b}_{t}\) follows the shifted exponential distribution with rate \(\mu_{i,t}\), which is defined as the _working rate_ of workers in group \(i\). It is assumed that workers having the same working rate form a group. In other words, workers in a group have the same computing capabilities.  
We model the working rate \(\mu_{i,t}\) as  
\[\mu_{i,t}:=e^{X_{i,t}} \tag{1}\]  
using a latent variable \(X_{i,t}\). Here, \(X_{i,t}\) denotes the ability of workers in group \(i\) for a subtask assigned at time \(t\).  
For workers in group \(i\), it is assumed that the zero state \(X_{i,0}\) follows the normal distribution \(\mathcal{N}(m,\sigma^{2})\), where \(m\) and \(\sigma\) are model parameters. Let us denote \(\theta=(m,\sigma)\). We write \(f_{0}\) as the probability density function of \(x_{i,0}\) given parameters,  
\[f_{0}(x_{i,0}|\theta=(m,\sigma))=\frac{1}{\sqrt{2\pi\sigma}}e^{-\frac{1}{2 \sigma}\left(x_{i,0}-m\right)^{2}}. \tag{2}\]  
The ability of workers may vary over time, which is formulated by  
\[X_{i,t}:=X_{i,t-1}+\epsilon_{i,t},\]  
where \(\epsilon_{i,t}\) is a white noise that is independent across group \(i\) and time \(t\) and follows the normal distribution with zero mean and variance \(\sigma_{\epsilon}^{2}\). Here, \(\epsilon_{i,t}\) represents the change in the worker ability as the time elapses from \(t-1\) to \(t\). In this work, we assume \(\sigma_{\epsilon}\) is given. For a precise formulation, we denote the distribution of \(X_{i,t}\) given \(X_{i,t-1}=x_{i,t-1}\) by  
\[f(x_{i,t}|x_{i,t-1})=\frac{1}{\sqrt{2\pi\sigma_{\epsilon}}}e^{-\frac{1}{2 \sigma_{\epsilon}^{2}}\left(x_{i,t}-x_{i,t-1}\right)^{2}}, \tag{3}\]  
which is the probability density function of the normal distribution with mean \(x_{i,t-1}\) and variance \(\sigma_{\epsilon}^{2}\).  
We assume that \(t_{j+1}-t_{j}\) is a sufficient time interval for the workers to carry out their subtasks allocated at time \(t_{j}\). We further assume that a task is assigned at successive time points spaced at uniform intervals, i.e., \(t_{j+1}-t_{j}=t_{l+1}-t_{l}\) for all \(j\
eq l\). Then, \(t_{0},t_{1},\ldots,t_{T}\) can be rewritten as \(0,1,\ldots,T\) for notational convenience.  
Let \(\eta_{i,j,l}\) be the observed variable that indicates the runtime of worker \(j\in[N_{i}]\) in group \(i\in[G]\) for a given data matrix  
\[A_{i,j,l}\in\mathbb{R}^{l_{i}\times d}\]  
with the following probability density function:  
\[p(\eta_{i,j,l}|X_{i,l},l_{i,t})=\frac{\mu_{i,t}}{l_{i,t}}e^{-\frac{\mu_{i,t}}{ l_{i,t}}(\eta_{i,j,l}-l_{i,t})}. \tag{4}\]  
Since \(\eta_{i,j,l}\)'s are independent, we obtain the probability density function \(g\) of the observation \(\eta_{i,t}\) given by  
\[g(\eta_{i,t}|x_{i,t},l_{i,t})=\prod_{t\in[T]_{0}}\prod_{j\in[N_{i}]}g(\eta_{i, j,t}|x_{i,t},l_{i,t}). \tag{5}\]  
for \(i\in[G]\), \(j\in[N_{i}]\), and \(t\in[T]_{0}\). It follows from (5) that we have the probability density function of \(\eta_{i,0,T}\) (observations for workers in group \(i\) through the time points \(t\in[T]_{0}\)) as follows:  
\[p(\eta_{i,0,T}|x_{i,0,T},l_{i,0,T})=\prod_{t\in[T]_{0}}g(\eta_{i,t}|x_{i,t},l_ {i,t}),\]  
where \(l_{i,0,T}\) and \(x_{i,0,T}\) denote the number of rows of the data matrix assigned to workers in group \(i\) and the ability of workers in group \(i\) at time \(t\in[T]_{0}\), respectively. Then, for all of the workers,  
\[p(\eta_{1:G,0,T}|x_{1:G,0:T},l_{1:G,0,T}) =\prod_{i\in[G]}\prod_{t\in[T]_{0}}g(\eta_{i,t}|x_{i,t},l_{i,t})\] \[=\prod_{i\in[G]}p(\eta_{i,0,T}|x_{i,0,T},l_{i,0,T}),\]  
where \(\eta_{1:G,0,T}\), \(x_{1:G,0,T}\), and \(l_{1:G,0,T}\) represent the overall observations, the workers' ability, and the number of rows of the assigned matrices for workers in group \(i\in[G]\) at time \(t\in[T]_{0}\), respectively.