  We consider a large distributed service system consisting of $n$ homogeneous
servers with infinite capacity FIFO queues. Jobs arrive as a Poisson process of
rate $\lambda n/k_n$ (for some positive constant $\lambda$ and integer $k_n$).
Each incoming job consists of $k_n$ identical tasks that can be executed in
parallel, and that can be encoded into at least $k_n$ "replicas" of the same
size (by introducing redundancy) so that the job is considered to be completed
when any $k_n$ replicas associated with it finish their service. Moreover, we
assume that servers can experience random slowdowns in their processing rate so
that the service time of a replica is the product of its size and a random
slowdown.
  First, we assume that the server slowdowns are shifted exponential and
independent of the replica sizes. In this setting we show that the delay of a
typical job is asymptotically minimized (as $n\to\infty$) when the number of
replicas per task is a constant that only depends on the arrival rate
$\lambda$, and on the expected slowdown of servers.
  Second, we introduce a new model for the server slowdowns in which larger
tasks experience less variable slowdowns than smaller tasks. In this setting we
show that, under the class of policies where all replicas start their service
at the same time, the delay of a typical job is asymptotically minimized (as
$n\to\infty$) when the number of replicas per task is made to depend on the
actual size of the tasks being replicated, with smaller tasks being replicated
more than larger tasks.
