Theory Lunch Seminar

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

Location:

ASA Conference Room 6115 Gates & Hillman Centers

Speaker:

KRISTY GARDNER, Ph.D. Student http://www.cs.cmu.edu/~ksgardne/

Event Website:

http://www.cs.cmu.edu/~theorylunch/20151007.html

For More Information, Contact:

dwajc@cs.cmu.edu

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.

Keywords:

Seminar Series