A little redundancy goes a long way: Convexity in redundancy systems

Redundancy is an increasingly popular technique for reducing response times in computer systems, and there is a growing body of theoretical work seeking to analyze performance in systems with redundancy. The idea is to dispatch a job to multiple servers at the same time and wait for the first copy to complete service. Redundancy can help reduce response time because redundant jobs get to experience the shortest of multiple queueing times and potentially of multiple service times-but it can hurt jobs that are not redundant and must wait behind the redundant jobs' extra copies. Thus in designing redundancy systems it is critical to find ways to leverage the potential benefits without incurring the potential costs. Scheduling represents one tool for maximizing the benefits of redundancy. In this paper we study three scheduling policies: First-Come First-Served (FCFS), Least Redundant First (LRF, under which less-redundant jobs have priority over more-redundant jobs), and Primaries First (PF, under which each job designates a "primary" copy, and all other copies have lowest priority). Our goal for each of these policies is to understand the marginal impact of redundancy: how much redundancy is needed to get the biggest benefit? We study this question analytically for LRF and FCFS, and via simulation for all three policies. One of our primary contributions is a surprisingly intricate proof that mean response time is convex as well as decreasing as the proportion of jobs that are redundant increases under LRF for exponential services. While response time under PF is also decreasing and appears to be convex as well, we find that, surprisingly, FCFS may be neither decreasing nor convex, depending on the parameter values. Thus, the scheduling policy is key in determining both whether redundancy helps and the marginal effects of adding more redundancy to the system. (C) 2019 Elsevier B.V. All rights reserved.