Worker Assignment for Multiple Masters to Speed Up Coded Distributed Computing in Heterogeneous Clusters

Abstract

In distributed computing systems, coding has played an important role to robustify the system against the effect of noise, e.g., stragglers, system failures and communication bottlenecks. Most of the existing work has focused on a simple master-worker model with one master and homogeneous workers. However, real-world systems are typically configured with heterogeneous workers distributed to computing nodes and serve multiple tasks in parallel. In this study, we consider the scenario in which multiple masters perform matrix multiplications using the workers having group heterogeneity. The group heterogeneity models that homogeneous workers are located in the same location and regarded as a group; the workers deployed in the different locations are potentially heterogeneous. We propose an asymptotically optimal worker assignment to multiple masters for coded distributed computing in the presence of heterogeneous groups of workers. Specifically, we present a lower bound for the expected latency in terms of the numbers of workers assigned to the masters and the amount of tasks allocated to workers. Adding the concentration constraints on the number of workers allocated to masters, we can obtain the minimum of the lower bound by taking the optimal worker assignment. We find the optimal worker assignment by converting the problem at hand into a linear programming problem. From both numerical simulations and experiments on Amazon EC2 clusters, we confirm that the effect of the proposed worker assignment is significant in various scenarios.