Abstract
Every time you go to the check-out counter in a supermarket, you have a decision to make: which queue do you join? Do you pick the queue with the fewest customers, the one with the least total number of items, pick a random queue, or do something entirely different? This question of picking the right queue so as to minimize mean response time is known as the “task assignment problem” and is a very old and classic problem in the performance modeling community. In this talk we examine task assignment in a new light, where there is server-side variability in addition to job-size variability. We ask how replication of jobs (sending a job to multiple queues) can help reduce response time in light of these two types of variability. We present several new results on the performance analysis of server farms under replication, including power-of-d replication and Join-Idle-Queue replication. Bottom Line: By the end of this talk, you will have a much better sense of what you should do at the supermarket :)