Computer Science Thesis Oral

— 1:30pm

Location:
In Person and Virtual - ET - McWilliams Classroom - Gates Hillman 4303 and Zoom

Speaker:
ZIV DAVID SCULLY , Ph.D. CandidateComputer Science DepartmentCarnegie Mellon University
https://ziv.codes/

A New Toolbox for Scheduling Theory

Queueing delays are ubiquitous in many domains, including computer systems, service systems, communication networks, supply chains, and transportation. Queueing and scheduling theory provide a rigorous basis for understanding how to reduce delays with scheduling, including evaluating policy performance and guiding policy design. Unfortunately, state-of-the-art theory fails to address many practical concerns. For example, scheduling theory seldom explicitly models nontrivial preemption limitations, and there is very little theory for scheduling in multiserver queues. We present two new, broadly applicable tools that greatly expand the reach of scheduling theory, using each to solve multiple open problems. The first tool, called “SOAP”, is a new unifying theory of scheduling in single-server queues, specifically the M/G/1 model. SOAP characterizes the delay distribution of a broad space of policies, most of which have never been analyzed before. Such policies include the Gittins index policy, which minimizes mean delay in low-information settings, and many policies with preemption limitations. The second tool, called “WINE”, is a new queueing identity that complements Little’s law. WINE enables a new method of analyzing complex queueing systems by relating them to simpler systems. This results in the first delay bounds for SRPT (shortest remaining processing time) and the Gittins index policy in multiserver queues, specifically the M/G/k model. Thesis Committee: Mor Harchol-Balter (Co-chair) Guy Blelloch (Co-chair) Alan Scheller-Wolf Anupam Gupta Adam Wierman (California Institute of Technology) Balaji Prabhakar (Stanford University) In Person and Zoom Participation. See announcement. [Rescheduled from 15 July 2022]

For More Information:
deb@cs.cmu.edu

Add event to Google
Add event to iCal