Delay and Stability Tradeoffs in Distributed Service Systems with Redundancy

We consider a large distributed service system with N servers that have random service rates, where there is a stream of incoming jobs that consist of K<<N identical tasks that can be executed in parallel. We assume that the K tasks from the same job can be encoded into R>K tasks of the same size (by introducing redundancy) so that the job is considered to be completed when *any* K out of the R tasks finish their service. 

 

From the point of view of a job, using more redundant tasks (i.e., using a larger R) can decrease the job's delay because it only has to wait for the tasks in the K fastest servers (out of the R) to finish their service. However, too many redundant tasks from all incoming jobs increase the overall congestion of the system, increasing the delay of all jobs (we can have a tragedy of the commons). Our goal is to characterize the minimum delay achievable in these systems and to design simple policies that achieve it.