We investigate the stability condition of redundancy- @math multi-server systems. Each server has its own queue and implements popular scheduling disciplines such as First-Come-First-Serve (FCFS), Processor Sharing (PS), and Random Order of Service (ROS). New jobs arrive according to a Poisson process and copies of each job are sent to @math servers chosen uniformly at random. The service times of jobs are assumed to be exponentially distributed. A job departs as soon as one of its copies finishes service. Under the assumption that all @math copies are i.i.d., we show that for PS and ROS (for FCFS it is already known) sending redundant copies does not reduce the stability region. Under the assumption that the @math copies are identical, we show that (i) ROS does not reduce the stability region, (ii) FCFS reduces the stability region, which can be characterized through an associated saturated system, and (iii) PS severely reduces the stability region, which coincides with the system where all copies have to be served. The proofs are based on careful characterizations of scaling limits of the underlying stochastic process. Through simulations we obtain interesting insights on the system's performance for non-exponential service time distributions and heterogeneous server speeds.
In redundancy systems with cancel-on-complete ( @math , as considered in this paper), once one of the copies has completed service, the other copies are deleted and the job is said to have received service. Most of the recent literature on redundancy has focused on @math and i.i.d. copies with FCFS as service policy implemented in the servers. For example, under these assumption, a thorough performance analysis has been carried out by @cite_15 @cite_21 , and as mentioned in the introduction, the stability condition has been fully characterized in @cite_15 @cite_22 . In @cite_15 , the authors consider a class-based model where redundant copies of an arriving job type are dispatched to a type-specific subset of servers, and show that the steady-state distribution has a product form. In @cite_21 , the previous result is applied to analyze a multi-server model with homogeneous servers where incoming jobs are dispatched to randomly selected @math servers. An important insight obtained there is that stability is not affected by @math and that the mean job delay in the system reduces as the redundancy degree @math increases.
@cite_15 @cite_21 @cite_22
2462681966 2604490148 2611196571
Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to run a request on multiple servers and wait for the first completion (discarding all remaining copies of the request). However, there is no exact analysis of systems with redundancy. This paper presents the first exact analysis of systems with redundancy. We allow for any number of classes of redundant requests, any number of classes of non-redundant requests, any degree of redundancy, and any number of heterogeneous servers. In all cases we derive the limiting distribution of the state of the system. In small (two or three server) systems, we derive simple forms for the distribution of response time of both the redundant classes and non-redundant classes, and we quantify the "gain" to redundant classes and "pain" to non-redundant classes caused by redundancy. We find some surprising results. First, the response time of a fully redundant class follows a simple exponential distribution and that of the non-redundant class follows a generalized hyperexponential. Second, fully redundant classes are "immune" to any pain caused by other classes becoming redundant. We also compare redundancy with other approaches for reducing latency, such as optimal probabilistic splitting of a class among servers (Opt-Split) and join-the-shortest-queue (JSQ) routing of a class. We find that, in many cases, redundancy outperforms JSQ and Opt-Split with respect to overall response time, making it an attractive solution. Redundancy is an important strategy for reducing response time in multi-server distributed queueing systems. This strategy has been used in a variety of settings, but only recently have researchers begun analytical studies. The idea behind redundancy is that customers can greatly reduce response time by waiting in multiple queues at the same time, thereby experiencing the minimum time across queues. Redundancy has been shown to produce significant response time improvements in applications ranging from organ transplant waitlists to Google’s BigTable service. However, despite the growing body of theoretical and empirical work on the benefits of redundancy, there is little work addressing the questions of how many copies one needs to make to achieve a response time benefit, and the magnitude of the potential gains. In this paper we propose a theoretical model and dispatching policy to evaluate these questions. Our system consists of k servers, each with its own queue. We introduce the Redundancy-d policy, u... We represent a computer cluster as a multi-server queue with some arbitrary graph of compatibilities between jobs and servers. Each server processes its jobs sequentially in FCFS order. The service rate of a job at any given time is the sum of the service rates of all servers processing this job. We show that the corresponding queue is quasi-reversible and use this property to design a scheduling algorithm achieving balanced fair sharing of the computing resources.