Theory Lunch Seminar

Wednesday, October 7, 2015 - 12:00pm to 1:00pm


ASA Conference Room 6115 Gates & Hillman Centers



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.

Event Website:

For More Information, Contact:


Seminar Series