# A Time-Series Model for Varying Worker Ability in Heterogeneous Distributed Computing Systems
###### Abstract  
In this paper, we consider the problem of estimating the time-dependent ability of workers participating in distributed matrix-vector multiplication over heterogeneous clusters. Specifically, we model the workers' ability as a latent variable and introduce a log-normally distributed working rate as a function of the latent variable with parameters so that the working rate increases as the latent ability of workers increases, and takes positive values only. This modeling is motivated by the need to reflect the impact of time-dependent external factors on the workers' performance. We estimate the latent variable and parameters using the expectation-maximization (EM) algorithm combined with the particle method. The proposed estimation and inference on the working rates are used to allocate tasks to the workers to reduce expected latency. From simulations, we observe that our estimation and inference on the working rates are effective in reducing expected latency. distributed computing; coded computation; expectation maximization algorithm; particle filtering; sequential Monte Carlo +
Footnote †: journal: Applied  
0000-0001-4993-3300-3300][PERSON] 0000-0001-4993-3300-3300-3300-3300-3300-3300-3300-3300-3300-3300-3300-3300-3300-3300-3300-33000  
computing capabilities, on average. Thus, the expected time to complete the entire task is highly dependent on the time for a worker with relatively small computing capabilities to finish the task. In other words, the uniform load allocation to workers without considering the heterogeneous characteristics of the workers' computing capabilities can lead to the performance degradation of computing systems. Reflecting on these points, research has been conducted under the assumption of heterogeneous clusters [15; 16]. In [15], the authors present an asymptotically optimal load allocation to minimize the expected task completion delay for fully heterogeneous clusters. Similarly, in [16], an optimal load allocation is proposed to minimize the expected execution time under the assumption of group heterogeneity, which means that workers in different groups have different latency statistics. In this work, we consider a scenario where the ability of each heterogeneous worker changes over time. While the work of [15; 16] covers distributed computation in a heterogeneous environment, the authors assume that each worker's ability is a fixed known constant. However, in reality, even workers designed to maintain a constant level of ability can have time-dependent abilities due to external factors such as changes in temperature and humidity over time [17]. If we do not estimate workers' abilities, the basic load allocation method would be the uniform load allocation, which assigns the same amount of tasks to each worker. However, as we mentioned earlier, this load allocation method can potentially lead to a loss of system performance. Thus, the estimation of workers' abilities is essential to improve system latency. We model the aggregated impact of such factors on the worker's ability as a normal distribution and set the worker's ability as a latent variable. As demonstrated in several prior works [3; 4; 6; 15; 16], it is widely accepted that the runtime of a worker is often modeled by an exponential distribution. We define the _working rate_ of a worker as the rate of the exponentially distributed runtime and assume that the working rate is log-normally distributed with two parameters: the mean and standard deviation of the logarithm of the working rate, respectively. The log-normal distribution is a good fit for the working rate since it ensures that the working rate takes only positive values and increases as the latent ability of a worker increases. We aim to estimate the latent variable and parameters associated with the ability/working rate of the worker so that one can properly allocate the workload on the workers in distributed computing.