Queueing with Redundant Requests: A more realistic model

Add to your list(s) Download to your calendar using vCal

• Mor Harchol-Balter - CMU
• Friday 16 September 2016, 11:00-12:00
• Auditorium, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

 Please be aware that this event may be recorded. Microsoft will own the copyright of any recording and reserves the right to distribute it as required

Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to replicate a request so that it joins the queue at multiple servers, where the request is considered complete as soon as any one copy of the request completes.

Redundancy is beneficial because it allows us to overcome server-side variability—the fact that the server we choose might be temporarily slow, due to factors like background load, network interrupts, garbage collection, and so on. When server-side variability dominates runtime, replicating requests can greatly reduce their response times.

In the past few years, queueing theorists have begun to study redundancy, first via approximations, and, more recently, via exact analysis. Unfortunately, for analytical tractability, all the theoretical analysis has assumed models where a job’s replicas each have independent service requirements, unrelated to the job’s inherent size. These unrealistic models have resulted in analysis which differs greatly from computer systems implementation results.

In this talk, we introduce a much more realistic model of redundancy. Our model allows us to decouple the inherent job size (X) from the server-side slowdown (S), where we track both S and X for each job. Analysis within the S&X model is, of course, much more difficult. Nevertheless, we derive a policy which is both analytically tractable within the S&X model and has provably excellent performance.

Joint work with: Kristy Gardner and Alan Scheller-Wolf.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Auditorium, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.