Jalani K. Williams

Setup Times in Multiserver Systems Degree Type: Ph.D. in Computer Science
Advisor(s): Weina Wang
Graduated: May 2024

Abstract:

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, CO₂ emissions, 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 many-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 J. Pender (Cornell University)
William A. Massey (Princeton University)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Queueing, multiserver systems, setup times, exceptional first service