  Master-worker distributed computing systems use task replication in order to
mitigate the effect of slow workers, known as stragglers. Tasks are grouped
into batches and assigned to one or more workers for execution. We first
consider the case when the batches do not overlap and, using the results from
majorization theory, show that, for a general class of workers' service time
distributions, a balanced assignment of batches to workers minimizes the
average job compute time. We next show that this balanced assignment of
non-overlapping batches achieves lower average job compute time compared to the
overlapping schemes proposed in the literature. Furthermore, we derive the
optimum redundancy level as a function of the service time distribution at
workers. We show that the redundancy level that minimizes average job compute
time is not necessarily the same as the redundancy level that maximizes the
predictability of job compute time, and thus there exists a trade-off between
optimizing the two metrics. Finally, by running experiments on Google cluster
traces, we observe that redundancy can reduce the compute time of the jobs in
Google clusters by an order of magnitude, and that the optimum level of
redundancy depends on the distribution of tasks' service time.
