Computer Science Thesis Oral
— 5:00pm
Location:
In Person and Virtual - ET
-
Reddy Conference Room, Gates Hillman 4405 and Zoom
Speaker:
JALANI K. WILLIAMS
,
Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://jalaniw.github.io/
Setup Times in Multiserver Systems
In many systems, servers do not turn on instantly; instead, a setup time must pass before a server can begin work. These “setup times” can wreak havoc on a system's queueing; this is especially true in modern systems, where servers are regularly turned on and off as a way to reduce operating costs (energy, labor, CO2, etc.). To design modern systems which are both efficient and performant, we need to understand how setup times affect queues.
Unfortunately, despite successes in understanding setup in the single server setting, setup in the multiserver setting remains poorly understood. To circumvent the main difficulty in analyzing multiserver setup, all existing results assume that setup times are memoryless, i.e. distributed Exponentially. However, in most practical settings, setup times are close to Deterministic, and the widely used Exponential-setup assumption leads to unrealistic model behavior and a dramatic underestimation of the true harm caused by setup times.
This thesis represents a comprehensive characterization of the average waiting time in a multiserver system with Deterministic setup times, the M/M/k/Setup-Deterministic. In particular, we derive multiplicatively-tight lower and upper bounds on the average waiting time, demonstrating that setup times, along with their distributions, can not be ignored; setup times can cause profound increases in waiting time, especially when the distribution of setup time has low variability. Our bounds are the first closed-form bounds on waiting time in any finite-server system with setup times, including the extensively-studied Exponential setup system. Furthermore, we use our bounds to derive a highly-accurate approximation, which we evaluate in a variety of settings. These results are made possible via our new method for bounding the expectation of a random time integral, called the Method of Intervening Stopping Times or MIST.
Thesis Committee:
Weina Wang (Chair)
Mor Harchol-Balter
Alan Scheller-Wolf
Jamol Pender (Cornell University)
Bill Massey (Princeton University)
In Person and Zoom Participation. See announcement.