A common technique for improving response time in queueing systems is the use of randomization. Algorithms frequently consider a small number of randomly selected options and choose the best of these options. This concept, often referred to as the power of d choices, is used in dispatching policies such as Join-the-Shortest-Queue-d.

In this paper we study the power of d choices in a new context: queueing in systems with redundant requests. In a system with redundant requests, each job that arrives to the system is copied and dispatched to multiple servers. As soon as the first copy is complete the job is considered complete, and all remaining copies are deleted. We study a theoretical model of redundancy, the Redundancy-d system, in which each job sends redundant copies to d servers chosen uniformly at random. While a great deal of empirical work has demonstrated the benefits of redundancy, there is no existing theoretical work that analyzes response time in the Redundancy-d system.

We derive the first exact expressions for mean response time in Redundancy-d systems with any finite number of servers. We also find asymptotically exact expressions for the distribution of response time as the number of servers approaches infinity.

28 pages

*Department of Mathematical Sciences, Carnegie Mellon University
**Tepper School of Business, Carnegie Mellon University

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu