Deadline-aware Load Allocation for Coded Computation over Heterogeneous Clusters

In large-scale distributed systems, the performance of computation tasks is often significantly degraded by straggling nodes. Recently, coded computation has emerged as a promising approach to mitigate the effect of stragglers. However, the performance of coded computation is still significantly affected by node workloads, particularly in heterogeneous clusters. Some load allocation schemes have been proposed to minimize the expected computation latency, but for time-sensitive tasks with strict deadlines, they often result in high failure probabilities. In this paper, we examine the fundamental matrix-vector multiplication tasks and focus on the deadline-aware load allocation problem under two typical runtime models, aiming to minimize the task failure probability. We firstly propose a simple yet effective normal approximation method based on the central limit theorem to approximate the failure probability, transforming the problem into a non-convex multivariate optimization, and then present an efficient iterative load allocation algorithm. Extensive simulations demonstrate the effectiveness of our proposed scheme.