Synergy via Redundancy
Gauri Joshi · ACM SIGMETRICS Performance Evaluation Review · 2018
The maximum possible throughput (rate of task completion) of a multi-server system is typically the sum of the service rates of individual servers. Recent works show that task replication can boost the throughput, in particular if the service time has high variability (Cv > 1). Thus, redundancy can be used to create synergy among servers such that their overall throughput is greater than sum of individual servers. This paper seeks to find the fundamental limit of this capacity boost achieved by task replication. The optimal adaptive replication policy can be found using a Markov Decision Process (MDP) framework, but the MDP is hard to solve in general. We propose two replication policies, MaxRate and AdaRep that gradually add replicas only when needed. To quantify the optimality gap of these policies, we also derive an a upper bound on the service capacity for the two-server case.