# A Time-Series Model for Varying Worker Ability in Heterogeneous Distributed Computing Systems
## 2 Preliminaries
### Optimal Load Allocation  
In this subsection, we provide an analysis of load allocation given \(\hat{\mu}_{i,t}\), for \(i\in[G]\) at time \(t\). The previous work [16] presents the optimal load allocation to minimize the expected task runtime. We reproduce the results in [16] with some definitions according to our system model. Let \(\mathcal{T}_{i}\) denote the task runtime taken to calculate the inner product of \(l_{i,t}\) rows of \(\mathbf{\Lambda}_{i,t}\) with \(\mathbf{\mathsf{b}}_{t}\) at a worker in group \(i\) at time \(t\). We assume that \(\mathcal{T}_{i}\)s are independent random variables, with the shifted exponential distribution as follows  
\[F_{i}[\eta]=\Pr[\mathcal{T}_{i}\leq\eta]=1-e^{-\frac{\eta_{i,t}}{l_{i,t}}\left( \eta-l_{i,t}\right)} \tag{6}\]  
for \(i\in[G]\) and \(\eta\geq l_{i,t}\). Here, it is assumed that the cumulative distribution function of the task runtime for a worker in group \(i\) to calculate one inner product is  
\[1-e^{\mu_{i,t}(\eta-1)}\]  
for \(\eta\geq 1\). Let \(\mathcal{T}_{r_{i,t}:N_{i}}^{l_{i,t}}\) denote the \(r_{i,t}\)-th order statistics of \(N_{i}\) random variables following the distribution in (6). We define  
\[\mathcal{T}=\max_{i\in[G]}\Bigl{\{}\mathcal{T}_{r_{i,t}:N_{i}}^{l_{i,t}} \Bigr{\}} \tag{7}\]as the task runtime for the master to finish the given task. **Theorem 1** (Theorem 2 in [16]). : _The optimal load allocation \((l_{1,t}^{*},l_{2,t}^{*},\ldots,l_{G,t}^{*})\) to achieve the minimum of_  
\[\max_{i\in[G]}\Bigl{\{}\mathrm{E}\Bigl{[}\mathcal{T}_{r_{i,t}:N_{i}}^{l_{i}} \Bigr{]}\Bigr{\}},\]  
_denoted by \(\mathcal{T}^{\star}\), is determined as follows:_  
\[l_{i,t}^{*}=\frac{k}{r_{i,t}^{*}+\sum_{j^{\prime}\in[G]}r_{j^{\prime},t}^{*} \frac{\xi(r_{j^{\prime},t}^{*}N_{i})}{\xi\left(r_{j^{\prime},t}^{*}N_{j^{\prime }}\right)}} \tag{8}\]  
_for \(i\in[G]\), where_  
\[r_{i,t}^{*}=N_{i}\left(1+\frac{1}{W_{-1}\Bigl{(}-e^{-\left(\mu_{i,t}+1\right) }\Bigr{)}}\right),\]  
\[\xi(r_{i,t}^{*},N_{i})=1+\frac{1}{\mu_{i,t}}\log\Bigl{(}-W_{-1}\Bigl{(}-e^{- \left(\mu_{i,t}+1\right)}\Bigr{)}\Bigr{)},\]  
_and_  
\[\frac{r_{i,t}^{*}}{\xi\left(r_{i,t}^{*},N_{i}\right)}=-\frac{\mu_{i,t}N_{i}}{ W_{-1}(-e^{-\left(\mu_{i,t}+1\right)})}.\]  
_Here, \(W_{-1}(x)\) is the lower branch of the Lambert \(W\) function. (\(W_{-1}(x)\) denotes the branch satisfying \(W(x)e^{W(x)}=x\) and \(W(x)\leq-1\)). Then the minimum expected execution time, \(\mathcal{T}^{\star}\), is represented as_  
\[-\frac{k}{\sum_{j\in[G]}\frac{\mu_{i,t}N_{i}}{W_{-1}\Bigl{(}-e^{-\left(\mu_{i, t}+1\right)}\Bigr{)}}}.\]  
Then, we have  
\[\mathrm{E}[\mathcal{T}]\geq\max_{i\in[G]}\Bigl{\{}\mathrm{E}\Bigl{[}\mathcal{ T}_{r_{i,t}:N_{i}}^{l_{i}}\Bigr{]}\Bigr{\}}\geq\mathcal{T}^{\star}.\]  
The first inequality follows from the definition of \(\mathcal{T}\) in (7) and the last inequality comes from Theorem 1. Next, we introduce the asymptotic behavior of the expected task runtime for the master to finish the given task as follows. **Theorem 2** (Theorem 3 in [16]). : _For the given optimal load allocation \((l_{1,t}^{*},l_{2,t}^{*},\ldots,l_{G,t}^{*})\), \(\mathrm{E}[\mathcal{T}]\) is asymptotically equivalent to \(\mathcal{T}^{\star}\) for a sufficiently large \(N\)._  
As we mentioned in Theorem 1, the optimal load allocation achieves the minimum of  
\[1-e^{\mu_{i,t}(\eta-1)}\]0  
denoted by \(\mathcal{T}^{\star}\). For the given \((\mu_{1,t},\mu_{2,t},\ldots,\mu_{G,t})\) and \((N_{1},N_{2},\ldots,N_{G})\), the constant \(\mathcal{T}^{\star}\) is a theoretical limit of \(\mathrm{E}[\mathcal{T}]\). From Theorem 2, we can conclude that the load allocation given by (8) is also optimal for \(\mathrm{E}[\mathcal{T}]\) from an asymptotical perspective for sufficiently large \(N\). **Remark 1**. : _For a fixed time \(t\), the working rate of workers \(\mu_{i,t}\) in group \(i\) is the rate parameter of the shifted exponential distribution. This implies that the expected execution time for a worker in group \(i\) to finish the given task is a linear function with respect to the reciprocal of the working rate.