Worker Assignment in Deadline-Aware Heterogeneous Distributed Computing Systems

Recently, distributed computing systems have become prevalent due to their capability to handle large-scale computations required by emerging machine learning algorithms and signal processing tasks. In real-world scenarios, these systems often encounter multiple tasks that must be completed within specific deadlines. Furthermore, service providers may offer different levels of service based on their users' subscription tiers. In this study, we focus on the assignment of workers in a heterogeneous coded distributed computing system that comprises multiple masters with distinct subscription tiers. Each master is responsible for a time-sensitive matrix-vector multiplication task that must be completed before a given deadline. The system receives rewards for finishing tasks prior to their deadlines and gives higher priority to tasks associated with higher subscription tiers. Our objective is to devise a worker assignment policy that maximizes the overall reward of the system. To achieve this, we propose a worker assignment policy called “reward greedy.” Through simulation results, we demonstrate that our proposed algorithm achieves performance very close to that of a brute-force search while exhibiting significantly lower complexity.