The Power of d Choices for Redundant Requests
October 7, 2015

A common strategy for improving a randomized algorithm's performance is to choose the best option out of d randomly selected alternatives, rather than simply making one random selection. For example, hash tables, quicksort, and join-the-shortest-queue (JSQ) dispatching all have "power-of-d-choices" variants. In this talk, we investigate the power of d choices in queueing systems with redundant requests, in which each job sends a copy of itself to d randomly chosen queues and waits for the first copy to complete. We derive exact closed-form expressions for mean response time in such systems as well as asymptotic expressions for mean response time in large systems, and we explore the effect of d on response time.

Joint work with Sam Zbarsky, Mor Harchol-Balter, and Alan Scheller-Wolf

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.